My friend wenx gives me a smart solution with O(n)-O(1) complexity. The idea is, first, we count the number of ones and zeros in the nums' lowest bit. If the ones beyond the normal number, we know that the lowest bit of the duplicate number is 1, otherwise is 0. Then in the next round, we will test the second lowest bit. In this round we will only test the numbers with the same lowest bit with the duplicate number( we have known it in the first round). And so on.

```
int findDuplicate(vector<int>& nums) {
int ret = 0;
int lowMask = 0;
for(int i=0;i<32;i++){
int mask = 1<<i;
int oneCnt = 0;
int zeroCnt = 0;
for(int j=0;j<nums.size();j++)if(i==0||ret==(nums[j]&lowMask)){
if((mask&nums[j])!=0)oneCnt++;
else zeroCnt++;
}
int allOne = 0;
for(int j=1;j<nums.size();j++)if(i==0||ret==(j&lowMask))if((mask&j)!=0)allOne++;
if(oneCnt>allOne)ret|=mask;
lowMask = (lowMask<<1)|1;
}
return ret;
}
```