寻找重复数

Trace

传送门：<https://leetcode-cn.com/problems/intersection-of-two-linked-lists/>

http://10.129.27.27/contest/9/problem/1002

Problem

Description

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

要求算法空间复杂度为 O(1) (不包括输入数组).

Input

输入包含两行, 第一行为一个正整数 n, 第二行为 n + 1 个正整数.

Output

输出为单独一行, 即所有给出的数中重复的数.

Sample Input 1

4
1 3 4 2 2

Sample Output 1

2

Sample Input 2

4
3 1 3 4 2

Sample Output 2

3

方法一：二分

我们用$cnt[i]$来记录原数组中小于等于$i$的个数，假设重复的数为$ans$，则1<i<ans时，cnt[i]<=i，ans<=i<=n时，cnt[i]>i；

已知答案一定在1到$n$之间，二分的思路是每次猜一个数$mid$，然后统计原数组中小于等于$mid$的个数$cnt$，利用上述性质进行二分。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // 二分
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid=(l+r)>>1;
            int cnt=0;
            for(int i=0;i<nums.size();i++){
                if(nums[i]<=mid){
                    cnt++;
                }
            }
            // 符合条件
            if(cnt>mid){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        return l;
    }
};

时间复杂度：$O(nlgn)$，空间复杂度$O(1)$。

方法二：位运算

我们定义数组$v1$，$v1[i]$记录数字1~n的二进制表示中，第$i$位为1的数量；

接着定义数组$v2$，$v2[i]$记录$nums$数组中所有数的二进制表示中，第$i$位为1的数量。

因为重复的数会多次出现，所以存在$i$，有$v1[i]>v2[i]$，所有这些$i$的二进制表示组成的和即为重复的数。

class Solution {
public:
    vector<int> v1;
    vector<int> v2;
    int findDuplicate(vector<int>& nums) {
        int n=nums.size();
		// 最大位数
        int bit_Max=0;
        int t=n-1;
        while(t){
            t>>=1;
            bit_Max++;
        }
        for(int i=0;i<bit_Max;i++){
            v1.push_back(0);
            v2.push_back(0);
        }
        for(int i=0;i<bit_Max;i++){
            for(int j=1;j<n;j++){
                if((j>>i)&1){
                    v1[i]++;
                }
            }
        }
        for(int i=0;i<bit_Max;i++){
            for(int j=0;j<nums.size();j++){
                if((nums[j])>>i&1){
                    v2[i]++;
                }
            }
        }
        int ans=0;
        for(int i=0;i<bit_Max;i++){
            if(v2[i]>v1[i]){
                ans=ans+(1<<i);
            }
        }
        return ans;
    }
};

时间复杂度：$O(nlgn)$，空间复杂度$O(1)$。