面试题3：数组中重复的数字

题目1：

在一个长度为n的数组所有数字都在0~n-1中，某些数字是重复的，某些数字不重复，判断是否有重复的数字，找出任意重复的数字。

• 思路：

1. 暴力遍历：o(n平方)
2. 先排序，排序后顺序遍历数组就可以找到重复的数字 o(nlogn)
3. 哈希表，遍历依次放入哈希表 时间o(n) 空间 o(n)
4. 因为所有元素都在0—n-1中，所以我们每遍历一个元素就把它和等于元素值的下标中的元素互换，让它“归位”，如果遍历到一个数和该数位置上的数一样，那么就重复了。 时间 o（n）空间o(1)

#include "stdafx.h"bool duplicate(int *data,unsigned int length,int *DuplicateNum)
{if (data == nullptr || length <= 1)//是否为有效输入return false;for (unsigned int i = 0; i < length; i++)//数组内的数是否在0到n-1中{if (data[i]<0 || data[i]>length - 1)return false;}for (unsigned int i=0;i<length;i++){unsigned int index = data[i];while (index!=i)//循环条件当前位置的元素数值不等于数组下标{if (index == data[index])//如果当前位置元素等于对应下标中的元素说明有重复数字{*DuplicateNum = index;return true;}unsigned int temp = data[index];//否则归位，调换位置data[index] = index;data[i] = temp;index = temp;}}return false;
}// ====================测试代码====================
bool contains(int array[], int length, int number)
{for (int i = 0; i < length; ++i){if (array[i] == number)return true;}return false;
}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))printf("Passed.\n");elseprintf("FAILED.\n");}elseprintf("Passed.\n");}elseprintf("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 functiontest("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 functiontest("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 functiontest("Test6", numbers, 0, duplications, sizeof(duplications) / sizeof(int), false);
}void main()
{test1();test2();test3();test4();test5();test6();return;
}

题目2：

在一个长度位n+1的数组里的所有数字都在1~n的范围内，至少有一个数字是重复的。找出任意的一个重复的数字，而且不能改变数组的位置。

-思路

1. 暴力遍历 o(n2)
2. 哈希表 o(n) o(n)
3. 我们看到在1-n的范围内一共有n个数字，而数组总数为n+1个，所以必然有一个数字是重复的，这个数字一定在1-n的范围内，所以我们在1-n的范围内进行二分查找o（logn），每一次二分如何判断取左还是取右呢？每一次二分我们可以计算1-mid和mid+1-n各自范围内出现次数（n+1个数字分到n个坑里，肯定有一边会多出数字），如果1~mid范围的数字小于mid，那么取mid+1,反之取另一边。o(nlogn) o(1)以时间换空间

#include "stdafx.h"
#include <exception>
#include <iostream>
using namespace std;//计算出现次数的函数
int CountRange(const int*data, int length, int start, int end)
{int count = 0;for (int i=0;i<length;i++){if (data[i] >= start&&data[i] <= end)count++;}return count;
}int getDuplication(const int * data, int length)
{if (data == nullptr || length < 2)throw exception("Invalid Parameters!");int start = 1;//start应该为数值范围的起始点而不是下标的起始点int end = length ;while (end>=start)//终止条件{int mid = (start + end) / 2;int CountLeft = CountRange(data, length, start, mid);//if (end == start)//{if (CountLeft > 1)return start;elsebreak;}if (CountLeft <= (mid - start + 1))start = mid + 1;elseend = mid;}return -1;
}// ====================测试代码====================
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){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));
}void main()
{test1();test2();test3();test4();test5();test6();test7();test8();test9();test10();
}