1. Description of the problem

Find the number of repeats

English description

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Follow-ups:

How can we prove that at least one duplicate number must exist in nums?

Can you solve the problem without modifying the array nums?

Can you solve the problem using only constant, O(1) extra space?

Can you solve the problem with runtime complexity less than O(n2)?

Example 1:

Input: nums = [1,3,4,2,2]

Output: 2

Example 2:

Input: nums = [3,1,3,4,2]

Output: 3

Example 3:

Input: nums = [1,1]

Output: 1

Example 4:

Input: nums = [1, 2] Output: 1

Constraints:

2 <= n <= 3 * 104

nums.length == n + 1

1 <= nums[i] <= n

All the integers in nums appear only once except for precisely one integer which appears two or more times.

Product description

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. Suppose there is only one repeating integer, find the repeating number.

Example 1:

Input: [1,3,4,2,2] output: 2

Example 2:

Input: [3,1,3,4,2] Output: 3

Description:

You cannot change the original array (assuming it is read-only). You can only use extra O(1) space. The time complexity is less than O(n2). There is only one duplicate number in the array, but it may be repeated more than once.

Second, the idea of solving the problem

Method one: dichotomy

1) Core algorithm

The conditions are given:

  • All numbers are within [1, n-1], where n is the array length;
  • There’s only one repeated number;

So the final answer, ANS, satisfies two conditions:

  1. The number of numbers in the array less than ANS, less than ANS itself; (Try a few more arrays.)
  2. Ans is the last number that satisfies condition 1;

Then we can do binary lookup based on ans condition above:

  • Determine mid according to the left and right boundaries, find the number of numbers in the array less than mid CNT; (If less than or equal to, the boundary update condition and ANS update position need to be adjusted)
  • Cntans = mid (the record may be a number for the answer);
  • CNT >=mid: right =mid;

2) Complexity proof

Time complexity: O(nlogn), where n is the length of nums[] array. Binary search requires two O(logn) times at most, and O(n) is required to traverse nums[] array to solve the number of numbers less than mid during each judgment. Therefore, the total time complexity is O(n logn).

Space complexity: O(1). We just need constant space for a few variables.

Method two: fast and slow pointer

1) Core algorithm

It’s a very clever mathematical idea:

We construct the graph for nums[] numbers, and each position I is connected with an edge of I →nums[I]. Since there are repeated digital targets, target must have at least two edges pointing to it, so there must be a ring in the whole picture, and the target we want to find is the entrance to the ring.

There are a few key questions:

1. Why does target have at least two edges pointing to it?

There are at least two positions I and j such that nums[I] == nums[j] == target, i.e.

2. Why must there be a ring?

The forward derivation is a little bit tricky, but you can think about conditions where there are no rings.

First, since the numbers in the array are [1, n] and the array size is n+1, the graph constructed from position 0 will never return to 0 again.

Nodes on the path starting from 0 have two choices:

  • Select the node in the path as the next node; (This makes a ring.)
  • Select a node outside the path as the next node. (This allows continuous expansion of the connection diagram starting from 0)

(That’s why you choose to start at 0.)

In order not to form a ring, there are two things to note:

  • In the connected graph formed from 0, position I and NUMs [I] are different (if they are the same, I →nums[I] itself, and since it is a connected graph, at least one other edge is also connected to NUMs [I], thus forming a ring).
  • Suppose there are 6 points in the link graph, and each point has a corresponding edge, so there are 6 edges in total. However, if there is no ring, the line formed by 6 points can only have 5 edges at most. Then where does the extra edge point to? Pointing to our answer, of course

So the condition is not true, there must be a ring in the graph!

3. Why is target the entrance to the ring?

There must be a ring in the graph starting from 0, and none of the nodes point to 0, so the graph should be clear.

​

4. How to find the entrance to the ring?

We first set slow and fast to take one step at a time and fast to take two steps at a time. According to (Floyd circle detection algorithm) the two Pointers will meet when there is a ring. At this point, we slow the starting point 0 again, and the two Pointers move one step at the same time each time, and the meeting point is the answer. (Picture source @ Li Kou)

An elegant mathematical proof (* ▽ *)

​

2) Complexity proof

Time complexity: O(n). The time complexity of Floyd loop detection algorithm is linear.

Space complexity: O(1). We just need constant space for a few variables.

Three, AC code

Method one: dichotomy

C++

class Solution { public: int findDuplicate(vector<int>& nums) { int left = 1, right = nums.size() - 1, ans = 0; while(left <= right){ // !!! Int mid = (left + right) >> 1; int smallNum = 0; for(int i = 0; i < nums.size(); i++){ smallNum += (nums[i] < mid) ? 1:0; } if(smallNum < mid){ left = mid + 1; ans = mid; } else right = mid - 1; } return ans; }};Copy the code

Java

class Solution { public int findDuplicate(int[] nums) { int left = 1, right = nums.length - 1, ans = 0; while(left <= right) { int mid = (left + right) >> 1; int cnt = 0; for(int x : nums){ cnt += (x < mid) ? 1:0; } if(cnt < mid) { left = mid + 1; ans = mid; } else { right = mid - 1; } } return ans; }}Copy the code

Method two: fast and slow pointer

C++

class Solution { public: int findDuplicate(vector<int>& nums) { int fast = 0, slow = 0; Do {fast = nums[nums[fast]]; // Double indexing equals two steps slow = nums[slow]; } while(slow ! = fast); slow = 0; While (nums[slow]! = nums[fast]){ slow = nums[slow]; fast = nums[fast]; } return nums[fast]; }};Copy the code

Java

class Solution { public int findDuplicate(int[] nums) { int slow = 0, fast = 0; do{ slow = nums[slow]; fast = nums[nums[fast]]; } while (slow ! = fast); slow = 0; while(nums[slow] ! = nums[fast]) { slow = nums[slow]; fast = nums[fast]; } return nums[slow]; }}Copy the code

Fourth, the problem solving process

【 Find the number of repeats 】

According to the requirements of the question, the time within O(N^2), space O(1), the original array is read-only, really can not think of a way, decisively to solve the problem area big man for help. ◑ man ◐

After understanding the general idea, I typed it again and modified it step by step in comparison with the efficient solution. The record is as follows :(only the dichotomy and fast and slow Pointers were tested. The binary method was too high-end to dare to see)

Method one: dichotomy

The first stroke

Left = mid + 1 / right = mid-1; left = mid + 1 / right = mid-1; left = mid + 1 / right = mid-1 It’s very possible to miss the answer when the border is drawn.

Therefore, repeatNum was added to record the number repetition times, and priority was given to judge whether it was greater than 1, so as to determine whether the algorithm was terminated.

class Solution { public: int findDuplicate(vector<int>& nums) { int left = 1, right = nums.size() - 1; while(left < right){ int mid = (left + right) >> 1; int smallNum = 0, repeatNum = 0; for(int i = 0; i < nums.size(); i++){ smallNum += (nums[i] < mid) ? 1:0; repeatNum += (nums[i] == mid) ? 1:0; } if(repeatNum > 1) return mid; if(smallNum < mid) left = mid + 1; else right = mid - 1; } return left; }};Copy the code

​

The second stroke

In fact, the above approach is constantly patch, extrusion, really not elegant.

Only after appreciating the official solution did the penny drop. O (*￣▽￣*)ブ ブ

Left = mid + 1 / right = mid – 1, left = mid + 1 / right = mid-1

class Solution { public: int findDuplicate(vector<int>& nums) { int left = 1, right = nums.size() - 1, ans = 0; while(left <= right){ // !!! Int mid = (left + right) >> 1; int smallNum = 0; for(int i = 0; i < nums.size(); i++){ smallNum += (nums[i] < mid) ? 1:0; } if(smallNum < mid){ left = mid + 1; ans = mid; } else right = mid - 1; } return ans; }};Copy the code

Method two: fast and slow pointer

The first stroke

Once you know the algorithm, programming is easy.

​

​