一、題目大意

給定一個包含 n + 1 個整數的數組 nums ，其數字都在 [1, n] 範圍內（包括 1 和 n），可知至少存在一個重複的整數。

假設 nums 只有 一個重複的整數 ，返回 這個重複的數 。

你設計的解決方案必須 不修改 數組 nums 且只用常量級 O(1) 的額外空間。

示例 1：

輸入：nums = [1,3,4,2,2]

輸出：2

示例 2：

輸入：nums = [3,1,3,4,2]

輸出：3

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一個整數 出現 兩次或多次 ，其餘整數均只出現 一次

進階：

• 如何證明 nums 中至少存在一個重複的數字?
• 你可以設計一個線性級時間複雜度 O(n) 的解決方案嗎？

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/...
著作權歸領釦網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

二、解題思路

這道題給我們n+1個數，所有的數都在[1, n]區域內，首先讓證明必定會有一個重複數，題目要求不能改變原數組，即不能給原數組排序，又不能用多餘空間，那麼hash的就不用考慮了，又要求時間小於O(n^2)，只能考慮用二分搜索法了，在區間[1, n]中搜索，首先求出中點mid，然後遍歷整個數組，統計所有小於等於mid的數的個數，如果個數小於等於mid，則説明重複值在[mid+1, n]之間，反之，重複值在[1, mid-1]之間，然後依次類推，直到搜索完成，此時的low就是我們要求的重複值。

三、解題方法

3.1 Java實現

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

四、總結小記

• 2022/10/25 旦行好事，莫問前程