以不变应万变

第一次的思路

我想的是：通过遍历numbers使得其下标和数值对应相等-（第一个循环），那么等遍历结束之后没有对应上的数值就是重复出现的数值（第二个循环）。

        for(int i=0;i<numbers.size();i++){
                    if(i!=numbers.at(i)) //如果下标不等于该下标对应的数字
                        swap(numbers[i],numbers[numbers[i]]); //交换该数字到对应的位置上
                }
        for(int i=0;i<numbers.size();i++){
            if(i!=numbers.at(i)) //如果下标不等于该下标对应的数字
                return(numbers.at(i));
        }
        return -1;

第一次的错误之处

Example

         raw_seq: 2 3 1 0 2 5 3
           index: 0 1 2 3 4 5 6
   processed_seq: 1 0 2 3 2 5 3

可以看到处理之后的数据，numbers[0]和0不相等，但是0并非重复出现的数字。

Description

虽然第i次循环都能把numbers[i]放到下标为numbers[i]的位置上，但是i位置又会有原来numbers[i]位置的数值填充，而这个数值不一定i。所以下标和数值不匹配的情况不仅仅有数值重复，还有i下标位置的数值不对应。

改进&更正

Code

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        
        int n=numbers.size();
        for(int i=0;i<n;i++){
            while(i!=numbers[i]){
                if(numbers[i]==numbers[numbers[i]]) return numbers[i];
                else swap(numbers[i],numbers[numbers[i]]);
            }
        }
        return -1;
    }
    
};

Description

遍历vector中每个元素，While循环直至第i个位置对应数字i，循环过程中比较numbers[i]和numbers[i]为下标的数字数值是否相等。如果相等，说明该数字重复出现，可以返回；如果不相等，交换二者位置，将numbers[i]放到下标为numbers[i]的位置。

我将这个过程称为：以不变应万变。

Reference

1. 数组中重复的数字

2. swap()用法