This is the 29th day of my participation in the August Wenwen Challenge.More challenges in August

A single element in an ordered array (Item number 540)

The title

Given an ordered array of integers, where every element appears twice and only one number appears only once, find the number. Example 1:

Enter: nums = [1.1.2.3.3.4.4.8.8] output:2
Copy the code

Example 2:

Enter: nums = [3.3.7.7.10.11.11] output:10
Copy the code

Tip:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

Advanced: Can the adopted scheme run in O(log n) time complexity and O(1) space complexity?

link

Leetcode-cn.com/problems/si…

explain

This one, this is a classic dichotomy.

A normal person’s first instinct would be to scan it, and of course you can get the final answer by scanning it, and it’s very simple, in order n time.

But there are two special cases that you have to pay attention to when you scan, when you have a single number in the head of the array or at the end of the array, which is nice, but what about the head of the array? Normally that’s fine, but when the array length is 1, the head of the array is also the tail of the array, so you still have a single element, so you have to do both.

So much for the sweep, now let’s see how bisection works.

Ordinary dichotomy is naturally unable to solve this problem, this problem is obviously a dichotomy variant.

Normal dichotomy direct comparison value can, no matter understand or operate rise very simple, but this problem is difficult to operate in varieties, otherwise should be simple problem.

So back to the problem, if you want to find the positions of individual elements, then you need to determine whether the odd even number is the length of the array, whether it’s odd or even.

Let’s think about it, because they’re saying that there’s only one element in the array, and all the other elements are paired, then the length of the array has to be odd.

In binary, every time the mid value is taken, it is necessary to find the corresponding mid to the same number. If it does not exist, it is directly GG, and the mid is a single number.

If there is, it is necessary to find the repeated number corresponding to mid, and then get the positions on both sides of the repeated number, divide it into the left interval and the right interval, and compare the length of the two intervals. Because the single number has not been found at this time, one of the left interval and the right interval must have an odd length.

Obviously, the single number is inside the odd number interval, so the left and right Pointers point to both ends of the odd number interval to create a new interval, and the subsequent operations are performed on this interval.

And then we do the same thing, we keep shortening the odd number until we find a single number.

The difference between this topic and the ordinary binary and one more thing, because will be out of a single array, and the length of the array than there will be an odd one even, so the final result will appear in the mid position, need not consider to find, if you cannot find, we need to increase a lot of code complexity, but don’t need.

Your own answer (traversal)

var singleNonDuplicate = function (nums) {
  if (nums[0] !== nums[1]) {
    return nums[0]}if (nums[nums.length - 2] !== nums[nums.length - 1]) {
    return nums[nums.length - 1]}for (let i = 1; i < nums.length; i++) {
    if(nums[i] ! == nums[i -1] && nums[i] ! == nums[i +1]) {
        returnnums[i]; }}};Copy the code

Scanning the method need not say much, everyone’s first reaction should be this method, the disadvantage is the space complexity is slightly higher, up to O(n).

A Better Way (two points)

Dichotomous thinking was explained in the explanation section, now look at the code 👇 :

var singleNonDuplicate = function (nums) {
    let left = 0
    let right = nums.length
    let L
    let R
    while (left <= right) {
        const mid = left + right >> 1
        if (nums[mid] === nums[mid + 1]) {
            L = mid
            R = mid + 1
        } else if (nums[mid] === nums[mid - 1]) {
            L = mid - 1
            R = mid
        } else {
            return nums[mid]
        }
        if (L % 2= = =0 && R % 2= =1) {
            left = mid + 1
        } else {
            right = mid - 1}}};Copy the code

Left represents the left pointer and right represents the right pointer. L and R are used to record the positions on both sides of mid, and then the positions of left and right Pointers are updated according to odd and even numbers to get the final answer.





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)