This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

Finding repetition number (Item No. 287)

The title

Given an array nums containing n + 1 integers, all of which are between 1 and n (including 1 and n), we know that there is at least one repeating integer.

Given that nums has only one repeating integer, find the repeating number.

You must design a solution that does not modify the array NUMs and uses only constant O(1) extra space.

Example 1:

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

Example 2:

Enter: nums = [3.1.3.4.2] output:3
Copy the code

Example 3:

Enter: nums = [1.1] output:1
Copy the code

Example 4:

Enter: nums = [1.1.2] output:1
Copy the code

Tip:

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums δΈ­ There’s only one integerappearTwo or more times, other integers only appearAt a time

Advanced:

  • How to provenumsIs there at least one duplicate number in?
  • You can design a linear time complexityO(n)Is the solution?

link

Leetcode-cn.com/problems/fi…

explain

This one. This one is autistic grass.

To be honest, three of the officially recommended ideas are completely out of the question, and the other two are also completely out of the question, leaving aside the second binary.

Title for example is very confusing, let a person feel Numbers are continuous, just is not the same as the order, this method is very simple, as long as the sweep time, to get the maximum and minimum value, the total number of all and at the same time, then in addition to the normal conditions was calculated by the maximum, minimum, and at this point in the second grade in school.

And then you divide the difference between the two sums by the number of extra numbers, and you’re done, and it’s very easy to get the final result.

But the title of his * is not like this ah, although the examples are continuous numbers, in fact, there may be a discontinuous situation, such as Jiang Aunt:

[1.4.4.2.4]
Copy the code

If this is the case, you obviously can’t use the summation method.

The only thing I can think of is to use a Map to cache the numbers that appear before and return the numbers that already exist.

That’s fine, but it’s not O(1) space, or it wouldn’t be medium.

Is there another way? Apparently there is, but it’s hard to imagine, and it took me a long time to understand.

First of all, two points. Two points? It’s not an ordered array. Why binary?

The author is also confused, and later found that this is for the value of the binary, what is the value of the binary?

Since they say that numbers must exist in the interval [1, n], then we can accumulate the number of numbers to achieve binary operation.

How do you say? If repeated numbers appear in [1, x], then the number of numbers appearing in the interval [1, x] must be larger than x, so that the number of numbers can be used to continuously narrow the interval, and finally narrow to a certain extent, is the final answer.

However, the time complexity of this scheme is O(nlogn), which is still not optimal.

The binary of the optimal solution is not said, the author is not very understand, the key lies in the double pointer.

Double pointer this can also be used by the author is also did not expect, the double pointer here is not the usual double pointer to narrow a range, but the fast or slow pointer.

The classic use of fast or slow Pointers is to determine whether a list is a circular list, but how can this array relate to a circular list?

Each element of the array represents the position that the element can go to. The value of the array represents the index. If you think of an array like this, you can think of the array as a linked list.

The solution of the fast and slow pointer is not described here, interested students can click here to see the details.

Your own answer (hash)

var findDuplicate = function(nums) {
  const set = new Set(a)for (let i = 0; i < nums.length; i++) {
    if (set.has(nums[i])) return nums[i]
    set.add(nums[i])
  }
};
Copy the code

The solution is simple and has no shortcomings except that it does not meet the requirements of the problem.

A Better Way (two points)

var findDuplicate = function(nums) {
  let left = 1
  let right = nums.length - 1
  while (left < right) {
    const mid = ~~((left + right) / 2)
    const sum = nums.reduce((count, item) = > count + (item <= mid ? 1 : 0), 0)
    if (sum > mid) {
      right = mid
    } else {
      left = mid + 1}}return left
};
Copy the code

The whole logic is classical binary logic, and the only thing that needs to be paid attention to is the value of sum. We need to accumulate all the numbers in the array that are less than or equal to the mid value.

A better way (two-pointer)

var findDuplicate = function(nums) {
    let slow = 0, fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow ! = fast); slow =0;
    while(slow ! = fast) { slow = nums[slow]; fast = nums[fast]; }return slow;
};
Copy the code

Here directly whoring the official answer, interested can click here to view the original answer.

Officials cleverly use do… While, if I hadn’t seen it, I wouldn’t have remembered JavaScript and do… While stuff.

With the do… The main reason for while is that the fast and slow Pointers overlap to begin with. If we use while, the loop doesn’t start at all, while do… The while is executed once anyway, after which the fast and slow Pointers point differently, and when they overlap a second time it terminates and the slow pointer is reset.

The second while is more normal, which is our second round of comparison. There is nothing to say.





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)