剑指 Offer 03. 数组中重复的数字

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/submissions/

方法1: 数组/哈希表 时间复杂度O(n) 空间复杂度O(n)

int findRepeatNumber(int* nums, int numsSize) {
    int i = 0;
    int* p = (int*)malloc(numsSize * sizeof(int));
    if (NULL == p) {
       return 0;
    }
    memset(p, 0, numsSize * sizeof(int));

    for (i = 0; i < numsSize; ++i) {
        ++p[nums[i]];

        if (p[nums[i]] > 1) {
           free(p);
           return nums[i];
        }
    }
    free(p);
    return 0;
}

方法2: 重排序数组，交换 时间复杂度O(n) 空间复杂度O(1)

从头到尾一次扫描这个数组中的每个数字。当扫描到下标i的数字时，首先比较这个数字 == i。
如果相等，就找到了一个重复的数字（该数组在下标为i和m的位置都出现了）
如果不相等，就把第i个数字和第m数字交换，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字。

int findRepeatNumber(int* nums, int numsSize){
    int i = 0;
    for (i = 0; i < numsSize; ++i) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }      
            /* swap */
            int temp    = nums[i];
            nums[i]     = nums[temp];
            nums[temp]  = temp;
        }  
    }
    return 0;
}