假設數組a有n個元素，元素取值范圍是1~n，如何判定數組是否存在重復元素

方法一：位圖法，原理是首先申請一個長度為n且均為’   

代碼如下：

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
bool xor_findDup(int * arr, int NUM)
{
	int *arrayflag = (int *)malloc(NUM*sizeof(int));
	int i = 1;
	while (i < NUM)
	{
		arrayflag[i] = false;
		i++;
	}
	for (i = 0; i < NUM; i++)
	{
		if (arrayflag[arr[i]] == false)
		{
			arrayflag[arr[i]] = true;
		}
		else
			return true;
	}
}
int main()
{
	int a[] = {1,7,4,2,1,4,3,1};	
	if (xor_findDup(a, 8))
		printf("存在重復元素");
	else
		printf("不存在重復元素");
	getchar();
	return 0;
}

　　方法二：對數組進行排序，然後比較相鄰的元素是否相同。C++標准庫提供了快速排序的方法qsort()，可以直接用的。

代碼如下：

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
int comp(const void *a, const void *b)
{
	return (*(int *)a = *(int *)b);
}
int isArrayRepeat(int *a, int n)
{
	int i = 0;
	if (!a || n < 1)
		return -1;
	qsort(a, n, sizeof(int), comp);
	for (i = 0; i < n - 1; i++)
	{
		if (a[i] == a[i + 1])
			return 1;
	}
	return 0;
}
int main()
{
	int result = -1;
	int a[10] = { 10, 9, 5, 4, 7, 6, 3, 2, 1, 9 };
	result = isArrayRepeat(a, 10);
	if (result)
		printf("yes\n");
	else
		printf("n0\n");
	getchar();
    return 0;
}

　　效果如圖：

方法三：遍歷數組，假設第i個位置的數字為i，則j的范圍為1~n。通過交換將j換到下表為j-1的位置上。直到所有數字都出現在自己對應的下標處，或發生了沖突，即該位置已經被占。此時的時間復雜度為O(n)。

代碼如下：

#include "stdafx.h"
#include <stdio.h>
int isArrayRepeat(int *a, int n)
{
	int j = -1;
	for (int i = 0; i < n; i++)
	{
		j = a[i];
		if (i == j - 1)
			continue;
		if (a[i] == a[j - 1])
			return 1;
		a[i] = a[j - 1];
		a[j - 1] = j;
		i--;
	}
	return 0;
}
void main()
{
	int result = -1;
	int a[10] = { 10, 9, 5, 4, 7, 6, 3, 2, 1, 9 };
	result = isArrayRepeat(a, 10);
	if (result)
		printf("yes\n");
	else
		printf("no\n");
	getchar();
}

　　效果如圖：