Problem 287: Find the Duplicate Number

思路

直观的思路就是用一个 HashSet 来存所有的元素，如果有重复就响应。这样的话，时间复杂度是 $O(n)$ ，空间复杂度是 $O(n)$
如果用 $O(1)$ 的空间如何解决呢？ - Binary Search!
先找出中间元素 mid，然后遍历整个数组，如果小于 mid 的元素的 count 大于 mid，说明在左半边有重复元素！反之，重复元素就在右边。

复杂度

时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$

public class Solution {
    public int findDuplicate(int[] nums) {
        int start = 1, end = nums.length - 1, mid;

        while (start < end) {
            mid = start + (end - start) / 2;

            int count = 0;
            for (int num : nums) {
                if (num <= mid) count++;
            }

            if (count > mid) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}

PreviousProblem 29: Divide Two Integers NextProblem 374: Guess Number Higher or Lower

Last updated 5 years ago

Was this helpful?

思路

直观的思路就是用一个 HashSet 来存所有的元素，如果有重复就响应。这样的话，时间复杂度是 $O(n)$ ，空间复杂度是 $O(n)$

如果用 $O(1)$ 的空间如何解决呢？ - Binary Search!

先找出中间元素 mid，然后遍历整个数组，如果小于 mid 的元素的 count 大于 mid，说明在左半边有重复元素！反之，重复元素就在右边。

复杂度

时间复杂度： $O(nlogn)$

空间复杂度： $O(1)$

public class Solution {
    public int findDuplicate(int[] nums) {
        int start = 1, end = nums.length - 1, mid;

        while (start < end) {
            mid = start + (end - start) / 2;

            int count = 0;
            for (int num : nums) {
                if (num <= mid) count++;
            }

            if (count > mid) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}