Neovim-如何使用编辑器的神

修改原数组找出重复数字

https://www.acwing.com/problem/content/14/

• 首先, 处理边界情况:

  • 如果数组是空, 直接返回.
  • 如果数组中有小于0, 或者大于等于$n$的数, 直接返回.

• 之后, 由于数组中的数值都在$[0, n - 1]$, 数组刚好可以排放成$nums[i] = i$这种形状.

  • 因此, 我们可以尝试先把数组排放成这种形状, 如果其中存在nums[i] = x, 并且x != i, 那么x一定是重复的数字.

• 从前向后遍历数组, 假设现在遍历到了nums[i] = x

  • 如果, nums[x] != x, 证明x还没摆放到正确位置, 这时直接交换nums[i]和nums[x]即可, 然后一直交换, 直到nums[nums[i]] = nums[i].
  • 此时, 如果nums[nums[i]] == nums[i]已经满足, 但是如果nums[i] != i, 证明nums[i]就是重复数字.
• 时间复杂度是$O(n)$.

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {

        if (nums.size() == 0) return -1;

        for (auto x : nums) {
            if (x < 0 || x >= nums.size()) return -1;
        }

        for (int i = 0; i < nums.size(); i ++) {
            while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if (nums[i] != i) return nums[i];
        }
        return -1;
    }
};

不修改原数组找到重复数字

https://www.acwing.com/problem/content/15/

• 一共有$n + 1$个坑, 但是要放$n$个取值范围为$[1, n]$的数, 一定有两个坑放的数字相等.

• 这里可以采用分治的做法:

  • 首先, 将数的取值范围分为$[1, \frac{n}{2}]$和$[\frac{n}{2} + 1, n]$.
  • 然后统计每个取值范围中有多少个数, 一定存在一个取值范围区间, 其中数的个数大于区间长度, 在这个区间中就有重复的数.
  • 然后继续递归, 直到递归的区间长度为1时, 这个数就是答案, 因为数的个数大于区间长度(1), 这个数一定重复出现.

• 时间复杂度是$O(nlogn)$, 空间复杂度是$O(1)$.

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {

        int l = 1, r = nums.size() - 1;

        while (l < r) {
            int mid = l + (r - l) / 2;

            int s = 0;
            for (auto x : nums) s += (x >= l) && (x <= mid);
            if (s > mid - l + 1) r = mid;
            else l = mid + 1;
        }

        return l;

    }
};