#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;
}
