题解 | #数组中重复的数字#

#include <cstdio>
#include <cstring>
#include <unistd.h>
class Solution {
  public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int array[], int length, int* duplication) {

        if ( array == NULL ) return false;

        // 判断数组是否合法（每个数都在0~n-1之间）
        for ( int i = 0; i < length; i++ ) {
            if ( array[i] < 0 || array[i] > length - 1 ) {
                return false;
            }
        }

        // key step
        int* assist = new int[length];
        memset(assist, 0, length);
        for (int i = 0 ; i < length ; i++) {
            if (assist[array[i]] == 1) {
                duplication[0] = array[i];
                return true;
            } else {
                assist[array[i]] = 1;
            }
        }

        return false;

    }
};

#include <cstdio>
class Solution {
  public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int nums[], int len, int* duplication) {
        for (int i = 0; i < len; i++) {
            while (i != nums[i]) {
                if (nums[i] == nums[nums[i]]) {
                    *duplication = nums[nums[i]];
                    return true;
                }

                // 交换 nums【i】 nums[nums[i]]
                int tmp;
                tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }
        }
        return false;
    }
};

一开始使用下标法，这种方法的弊端就是没法满足返回第一个重复的数字的要求，

只好换成辅助空间的方法，用下标法有解决办法的话浇一下，，，

下面说一下两种方法中遇到的坑：

1. 辅助空间：
1. new出来的数组各元素数值随机，使用memset但各元素没有变成0（debug得到的），本来的判断条件是assist[array[i]] ！= 0，但由于上述原因，改成了assist[array[i]] == 1
2. 下标法
1. 在做assist[array[i]]和assist[i]的数值交换时，一定要先赋值assist[array[i]]，因为assist[array[i]]的索引需要assist[i]的存在，假如先赋值了array[i]，则索引出来的assist[array[i]]和我们预想的不一样了