Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/287.html

 287	Find the Duplicate Number

 Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive),
 prove that at least one duplicate number must exist.

 Assume that there is only one duplicate number, find the duplicate one.

 Example 1:

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

 Example 2:

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

 Note:
     You must not modify the array (assume the array is read only). => 不能给原数组排序
     You must use only constant, O(1) extra space. => 不能哈希表
     Your runtime complexity should be less than O(n^2). => 不能用 brute force
     There is only one duplicate number in the array, but it could be repeated more than once.

 @tag-array
 @tag-binarysearch

Algorithm

Using the binary search method, search in the interval [1, n], first find the midpoint mid, then traverse the entire array, count all the numbers less than or equal to mid,

  • If the number is less than or equal to mid, the repeated value is between [mid+1, n],
  • On the contrary, the repeated value should be between [1, mid-1], Until the search is completed, low index then is the repeated value we require.

Bit

For each digit, the number of 1s in this digit in all numbers from 0 to n-1 should be fixed. If there are more 1s in this digit in all numbers in the nums array, it means that the this 1 is in duplicated number. We can reproduce the repeated number by adding up all the 1 bits of the repeated number.

Code

  • import java.util.Arrays;

public class Find_the_Duplicate_Number {

    class Solution_bit {
        public int findDuplicate(int[] nums) {
            int res = 0, len = nums.length;
            for (int i = 0; i < 32; ++i) {
                int bit = (1 << i), cnt1 = 0, cnt2 = 0;
                for (int k = 0; k < len; ++k) { // len is actually n+1
                    if ((k & bit) > 0) ++cnt1; // 1s count with no duplicate
                    if ((nums[k] & bit) > 0) ++cnt2; // 1s count with no duplicate
                }
                if (cnt2 > cnt1) res += bit;
            }
            return res;

        }
    }

    class Solution {
        public int findDuplicate(int[] nums) {
            int left = 1, right = nums.length;
            while (left < right) {
                int mid = left + (right - left) / 2, cnt = 0;
                for (int num : nums) {
                    if (num <= mid) ++cnt;
                }
                // eg. 1,1,1,1,1,1,1,2
                // eg. 1,2,2,2,2,2,2,2
                if (cnt <= mid) left = mid + 1;
                else right = mid;
            }
            return right;
        }
    }

    class Solution_sort {
        public int findDuplicate(int[] nums) {
            Arrays.sort(nums);
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == nums[i-1]) {
                    return nums[i];
                }
            }

            return -1;
        }
    }
}

  • // OJ: https://leetcode.com/problems/find-the-duplicate-number/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int findDuplicate(vector<int>& A) {
        int L = 1, R = A.size() - 1;
        while (L < R) {
            int M = (L + R) / 2, cnt = 0;
            for (int n : A) cnt += n <= M;
            if (cnt <= M) L = M + 1;
            else R = M;
        }
        return L;
    }
};

  • class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left, right = 1, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            cnt = sum(v <= mid for v in nums)
            if cnt > mid:
                right = mid
            else:
                left = mid + 1
        return left

############

class Solution(object):
  def findDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums) - 1
    start, end = 1, n
    while start + 1 < end:
      mid = start + (end - start) / 2
      count = 0
      for num in nums:
        if num < mid:
          count += 1
      if count >= mid:
        end = mid
      else:
        start = mid
    if nums.count(start) > nums.count(end):
      return start
    return end

All Problems

All Solutions