287. Find the Duplicate Number

1. 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 repeated number in nums, return this repeated number.

2. Example

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,1,2]
Output: 1

3. Constraints

• 2 <= n <= $3 * 10^4$
• 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.

4. Follow Up

• 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($n^2$)?

5. Solutions

Array (Follow Up)

n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// put every element to its correct position
// for example, the index of '1' should be 0, while the index of '6' should be 5

// if we don't want to change the arrat, we could use fast-slow pointers methord
// if there is a duplicate number, there will be a loop, and pointers will meet
class Solution {
public:
    // int findDuplicate(vector<int>& nums)
    int findDuplicate(vector<int>& m_nums) {
        for (int i = 0; i < m_nums.size(); ++i) {
            while (m_nums[i] != i + 1) {
                if (m_nums[m_nums[i]] == m_nums[m_nums[i]] + 1) {
                    return m_nums[i];
                } else {
                    swap(m_nums[i], m_nums[m_nums[i]]);
                }
            }
        }

        return 0;  // for compile check
    }
};