算法practice1进阶

7次阅读

没有评论

这两个方案是面试中常见的进阶考向，尤其是当面试官追加限制条件（如“不准修改原数组”）时，方案 B 是区分普通候选人和优秀候选人的关键。

这是最直观的解法。利用 HashSet 查找元素时间复杂度为 $O(1)$ 的特性，遍历数组并记录已出现的数字。

初始化一个空的 HashSet。
遍历数组中的每一个数字 num：
- 如果 num 已经在 Set 中，说明它是重复的，直接返回。
- 如果不在，将 num 加入 Set。
遍历结束仍未发现重复，返回 -1。

时间复杂度： $O(n)$ 。只需遍历一次数组。
空间复杂度： $O(n)$ 。最坏情况下（没有重复或重复在最后），需要存储 $n-1$ 个数字。

这个方案非常巧妙。通常二分法是基于下标搜索，但这里的二分是基于数值范围搜索。

前提条件：题目中提到数字范围在 $1 \sim n-1$ （注意：如果包含 $0$ ，逻辑稍作调整，但原理一致）。

如果 $1 \sim n-1$ 范围内没有重复数字，那么 $1 \sim m$ 这个范围内的数字应该刚好只有 $m$ 个。如果统计发现这个范围内的实际数字个数超过了 $m$ ，那么重复数字一定在 $1 \sim m$ 之间。

确定范围：初始范围 low = 1, high = 7，中间值 mid = 4。
统计次数：遍历整个数组，计算数值在 $1 \sim 4$ 范围内的数字个数。
二分收缩：
- 如果统计个数 > 4，说明重复数字在 $1 \sim 4$ 之间，令 high = 4。
- 如果统计个数 <= 4，说明重复数字在 $5 \sim 7$ 之间，令 low = 5。
循环结束：当 low == high 时，就找到了其中一个重复数字。

Java

public int getDuplicate(int[] nums) {
    int low = 1;
    int high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int count = countRange(nums, low, mid);
        if (low == high) {
            if (count > 1) return low;
            else break;
        }
        if (count > (mid - low + 1)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

private int countRange(int[] nums, int low, int mid) {
    int count = 0;
    for (int num : nums) {
        if (num >= low && num <= mid) count++;
    }
    return count;
}

时间复杂度： $O(n \log n)$ 。二分查找需要 $\log n$ 次，每次都需要 $O(n)$ 时间遍历数组统计次数。
空间复杂度： $O(1)$ 。只使用了常数个变量，且没有修改原数组。

方案	时间复杂度	空间复杂度	是否修改原数组	适用场景
原地置换	$O(n)$	$O(1)$	是	追求极致性能，允许修改输入。
HashSet	$O(n)$	$O(n)$	否	内存充足，追求代码简洁。
二分法	$O(n \log n)$	$O(1)$	否	内存极其受限，且禁止修改原数组。