找出數組中重復的數字（c語言）

讓人瑟瑟發抖的面試題
。
。
。

來我們看一下題目
在一個 長度為n的數組里的所有數字都在0~n-的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復倫理，也不知道每個數字重復了多少次，找出任意一個重復的數字
注意：時間復雜度O（n），空間復雜度O(1)

怎么解決勒？？？
分析：利用題目中0~n-1范圍，可以運用數組下標和數組內容進行比較
if (arr[i] != arr[arr[i]])，如果不相等時，進行調換，相等時，直接返回值
來看看代碼

#include<stdio.h>
#define SIZE(arr) sizeof(arr)/sizeof(arr[0])//數組長度

void Swap(int *left, int *right)
{
    int tmp = *left;
    *left = *right;
    *right = tmp;
}
int duplicate(int arr[],int len)
{
    int i;
    if (len < 0)
    {
        return 0;
    }
    for (i = 0; i < len; i++)
    {
        if (arr[i] < 0 || arr[i]>len - 1)//限定數字大小
        {
            return 0;
        }
        while (arr[i] != i)
        {
            if (arr[i] != i)
            {
                if (arr[i] != arr[arr[i]])//數組中數字是否等于以數字為下標的數字
                {
                    Swap(&arr[i], &arr[arr[i]]);
                }
                else
                {
                    return arr[i];
                }
            }
        }
    }
    return 0;
}
int main()
{
    int arr[] = {2,3,1,0,2,5,3};
    printf("%d", duplicate(arr, SIZE(arr)));
    return 0;
}

總結：數組中數據給定范圍之后，可以多利用下標 i 進行求解