- // 面试题 3(一): 找出数组中重复的数字, 可修改数组
- // 题目: 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内. 数组中某些数字是重复的, 但不知道有几个数字重复了,
- // 也不知道每个数字重复了几次. 请找出数组中任意一个重复的数字. 例如, 如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3},
- // 那么对应的输出是重复的数字 2 或者 3.
- #include <iostream>
- using namespace std;
- bool duplicate(int* numbers, int length, int& num)
- {
- // 鲁棒性测试 1. 空指针或者长度无效 2. 超出 0 到 n-1 范围
- // 问题 1: 少考虑了 length<=0
- if (numbers == nullptr || length <= 0)
- {
- return false;
- }
- for (int i = 0; i <length; ++i)
- {
- if (numbers[i] < 0 || numbers[i]> length - 1)
- {
- return false;
- }
- }
- // 主要思想: 数组范围 [0, n-1], 无重复情况 numbers[i] = i
- // 将 numbers[i] 与其对应位置值做对比, 如果相等则为重复值, 如不等交换值.
- for (int i = 0; i < length; ++i)
- {
- while (numbers[i] != i) // 在本位置的跳过
- {
- if (numbers[i] == numbers[numbers[i]]) // 与其位置值相等
- {
- num = numbers[i];
- return true;
- }
- // 不相等, 交换值
- int temp = numbers[i]; //temp 为位置索引
- numbers[i] = numbers[temp];
- numbers[temp] = temp;
- // 问题 2: 没有注意赋值顺序
- //int temp = numbers[numbers[i]]; // 如先赋给 numbers[i]
- //numbers[numbers[i]] = numbers[i]; // 则 numbers[numbers[i]] 值非预期更改
- //numbers[i] = 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(const 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");
- 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();
- system("pause");
- }
- //sizeof(numbers) / sizeof(int) 计算数组大小很巧妙
来源: http://www.bubuko.com/infodetail-3462108.html