//源代码 #include //定义一个布尔函数：有重复值返回true，否则返回false //子函在前，主函里就不用声明了 bool duplicate(int numbers[], int length, int* duplication) { //无效值特殊处理 if(numbers == nullptr || length <= 0) return false; //非法输入特殊处理 for(int i = 0; i < length; ++i) { if(numbers[i] < 0 || numbers[i] > length - 1) return false; } //操作 for(int i = 0; i < length; ++i) { //这里对于num[i]与i的值用了while判断 while(numbers[i] != i) { if(numbers[i] == numbers[numbers[i]]) { *duplication = numbers[i]; return true; //有重复值则返回true }// 交换numbers[i]和numbers[numbers[i]] int temp = numbers[i]; numbers[i] = numbers[temp]; numbers[temp] = temp; } }return false; }// ====================测试代码==================== //这是啥？答：为了验证这个重复值是否是预期array里重复了的值 bool contains(int array[], int length, int number) { for(int i = 0; i < length; ++i) { if(array[i] == number) return true; }return false; } //测试函数 //testName表测试几 //expected[]表期望结果值，也就是都有哪个值给重复了 //expectedExpected表期望结果值的sizeof //validArgument表示有没有重复的函数 void test(char* testName, int numbers[], int lengthNumbers, int expected[], int expectedExpected, bool validArgument) { //输出一串字：表示测试几开始了 printf("%s begins: ", testName); //调用这个布尔函数 int duplication; bool validInput = duplicate(numbers, lengthNumbers, &duplication); if(validArgument == validInput)//看输入是否有效 { if(validArgument) { if(contains(expected, expectedExpected, duplication))//duplication是之前duplicate(numbers, lengthNumbers, &duplication); 里的 printf("Passed.\n"); else printf("FAILED.\n"); } else printf("Passed.\n"); } else printf("FAILED.\n"); }// 重复的数字是数组中最小的数字 void test1() { int numbers[] = { 2, 1, 3, 1, 4 }; //发现了吗？空括号可以这么去定义 int duplications[] = { 1 }; test("Test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true); }// 重复的数字是数组中最大的数字 void test2() { int numbers[] = { 2, 4, 3, 1, 4 }; int duplications[] = { 4 }; test("Test2", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true); }// 数组中存在多个重复的数字 void test3() { int numbers[] = { 2, 4, 2, 1, 4 }; int duplications[] = { 2, 4 }; test("Test3", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true); }// 没有重复的数字 void test4() { int numbers[] = { 2, 1, 3, 0, 4 }; int duplications[] = { -1 }; // not in use in the test function test("Test4", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), false); }// 没有重复的数字 void test5() { int numbers[] = { 2, 1, 3, 5, 4 }; int duplications[] = { -1 }; // not in use in the test function test("Test5", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), false); }// 无效的输入 void test6() { int* numbers = nullptr; int duplications[] = { -1 }; // not in use in the test function test("Test6", numbers, 0, duplications, sizeof(duplications) / sizeof(int), false); }void main() { test1(); test2(); test3(); test4(); test5(); test6(); }

1. 思路1：新建一个数组array来复制输入的数组，对应的数放在该对应下标位置处，要是有重复的值立马就能找到。
2. 思路2：利用二分查找法解决，这也是书中的方法。例如长为8的数组{2 3 5 4 3 2 6 7}，数字范围在1-7内，中间数字4将其分为1-4和5-7。统计1-4在整个数组中出现的次数，若大于4，则必定有重复数。将1-4继续分成1-2和3-4，统计1-2在整个数组中的次数为2；再统计3-4在整个数组中出现的次数为3，所以3和4里必定有一个数是重复数，这样就找到了。

定义数组*num,长度n+1，新数组*Array; 输入长度n+1； 遍历输入数组num； 遍历输入数组Array[]并初始化为0; //特殊处理 输入无效的情况； 数组里的值超范围的情况； //处理 遍历num[]： 比较array[i]的值与num[i]的值，若不一样： 将num[i]放到Array[num[i]]处； 否则： 这个num[i]的值就是那个重复的值,赋值给结果r； break； 输出r； return 0;

#include using namespace std; int main() { int *num,*Array; int n, r=0; scanf("%d", &n); num = (int*)malloc(sizeof(int)*n); Array = (int*)malloc(sizeof(int)*n); for(int i=0; in-1) return 1; } //特殊处理 if(num==nullptr || n<=0) return 1; //操作 for(int i=0; i