# 剑指第三题:数组重复数字 不修改数组

xiaoxiao2021-02-28  14

#include <iostream> #include <cstdlib> #include <stdio.h> //数组长度n+1，内容为1到n的数字，有重复 //二分法 数组中重复数字 不能修改数组内容 时间复杂度O(nlogn) 空间复杂度O(1) int count(int* numbers,int length,int start,int end); int getDuplication(int* numbers, int length){ if(length <= 0 || numbers == nullptr) return -1; //i make mistake here for using return false as return 0; int start=1,end=length; int i=0; while(end>=start){ int middle=start+((end - start) >> 1); //i make mistake here with +1 int range = count(numbers,length,start,middle); if(end == start){ if(range){ return start; } else return -1; } if(range){ end = middle; } else start = middle +1; } } int count(int* numbers,int length,int start,int end){ if(numbers == nullptr || end < start) return false; int countrange=0; for(int i=0;i<length;i++){ if(numbers[i]>=start && numbers[i]<=end){ countrange++; } } if(countrange > (end-start+1)) return 1; else return 0; } void test(const char* testName, int* numbers, int length, int* duplications, int dupLength) { int result = getDuplication(numbers, length); for (int i = 0; i < dupLength; ++i) { printf("result=%d,du=%d\n",result,duplications[i]); if (result == duplications[i]) { std::cout << testName << " passed." << std::endl; return; } } std::cout << testName << " FAILED." << std::endl; } void test1() { int numbers[] = { 2, 3, 5, 4, 3, 2, 6, 7 }; int duplications[] = { 2, 3 }; test("test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test2() { int numbers[] = { 3, 2, 1, 4, 4, 5, 6, 7 }; int duplications[] = { 4 }; test("test2", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test3() { int numbers[] = { 1, 2, 3, 4, 5, 6, 7, 1, 8 }; int duplications[] = { 1 }; test("test3", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test4() { int numbers[] = { 1, 7, 3, 4, 5, 6, 8, 2, 8 }; int duplications[] = { 8 }; test("test4", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test5() { int numbers[] = { 1, 1 }; int duplications[] = { 1 }; test("test5", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test6() { int numbers[] = { 3, 2, 1, 3, 4, 5, 6, 7 }; int duplications[] = { 3 }; test("test6", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test7() { int numbers[] = { 1, 2, 2, 6, 4, 5, 6 }; int duplications[] = { 2, 6 }; test("test7", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test8() { int numbers[] = { 1, 2, 2, 6, 4, 5, 2 }; int duplications[] = { 2 }; test("test8", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test9() { int numbers[] = { 1, 2, 6, 4, 5, 3 }; int duplications[] = { -1 }; test("test9", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int)); } void test10() { int* numbers = nullptr; int duplications[] = { -1 }; test("test10", numbers, 0, duplications, sizeof(duplications) / sizeof(int)); } int main() { test1(); test2(); test3(); test4(); test5(); test6(); test7(); test8(); test9(); test10(); system("pause"); return 0; }