題目一：找出陣列中重復的數字，在一個長度為n的陣列里的所有數字都在0~n-1的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字，例如，如果輸入長度為7的陣列{2, 3, 1, 0, 2, 5, 3}，那么對應的輸出是重復的數字2或者3，
測驗用例：
- 長度為n的陣列里包含一個或多個重復的數字，
- 陣列中不包含重復的數字，
- 無效輸入測驗用例（輸入空指標；長度為n的陣列中包含0~n-1之外的數字）
測驗代碼：
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");
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);
}
本題考點：
- 考查應聘者對以為陣列的理解及編程能力，一維陣列在記憶體中占據連續的空間，因此我們可以根據下標定位對應的元素，
- 考查應聘者分析問題的能力，當應聘者發現問題比較復雜時，能不能通過具體的例子找出其中的規律，是能否解決這個問題的關鍵所在，
解法：
- 先把輸入的陣列排序，再從頭掃描排序后的陣列就可以了，排序一個長度為n的陣列需要O(nlogn)的時間，
- 利用哈希表，時間復雜度O(n)，空間復雜度O(n)，
- 最優解可以做到時間復雜度O(n)，空間復雜度O(1)，
我們注意到陣列中的數字都在0~n-1的范圍內，如果這個陣列中沒有重復的數字，那么當陣列排序之后數字i將出現在下標為i的位置，由于陣列中有重復的數字，有些位置可能存在多個數字，同時有些位置可能沒有數字，
現在讓我們重排這個陣列，從頭到尾以此掃描這個陣列中的每個數字，當掃描到下標為i的數字時，首先比較這個數字（用m表示）是不是等于i，如果是，則接著掃描下一個數字；如果不是，則再拿它和第m個數字進行比較，如果它和第m個數字相等，就找到了一個重復的數字（該數字在下標為i和m的位置都出現了）；如果它和第m個數字不相等，就把第i個數字和第m個數字交換，把m放到屬于它的位置，接下來再重復這個比較、交換的程序，知道我們發現一個重復的數字，
example:
{2, 3, 1, 0, 2, 5, 3} ->{1, 3, 2, 0, 2, 5, 3}->{3, 1, 2, 0, 2, 5, 3}->{0, 1, 2, 3, 2, 5, 3}
實作代碼：
#include <cstdio>
// 引數:
// numbers: 一個整數陣列
// length: 陣列的長度
// duplication: (輸出) 陣列中的一個重復的數字
// 回傳值:
// 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)
{
while(numbers[i] != i)
{
if(numbers[i] == numbers[numbers[i]])
{
*duplication = numbers[i];
return true;
}
// 交換numbers[i]和numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = 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;
}
int main()
{
test1();
test2();
test3();
test4();
test5();
test6();
return 0;
}
題目二：不修改陣列找出重復的數字，在一個長度為n+1的陣列里的所有數字都在1~n的范圍內，所以陣列中至少有一個數字是重復的，請找出陣列中任意一個重復的數字，但不能修改輸入的陣列，例如，如果輸入長度為8的陣列{2， 3， 5， 4， 3， 2， 6， 7}，那么對應的輸出是重復的數字2或者3，
測驗用例：
- 長度為n+1的陣列里包含一個或多個重復的數字，
- 陣列中不包含重復的數字，
- 無效輸入測驗用例（輸入空指標；長度為n的陣列中包含1~n之外的數字），
測驗代碼：
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));
}
本題考點：
- 考查應聘者對以為陣列的理解及編程能力，以為陣列在記憶體中占據連續的空間，因此我們可以根據下標定位對應的元素，
- 考查應聘者對二分查找演算法的理解，并能快速、正確地實作二分查找演算法的代碼，
- 考查應聘者的溝通能力，應聘者只有具備良好的溝通能力，才能充分了解面試官的需求，從而有針對性地選擇演算法解決問題，
實作代碼：
#include <iostream>
int countRange(const int* numbers, int length, int start, int end);
// 引數:
// numbers: 一個整數陣列
// length: 陣列的長度
// 回傳值:
// 正數 - 輸入有效，并且陣列中存在重復的數字，回傳值為重復的數字
// 負數 - 輸入無效，或者陣列中沒有重復的數字
int getDuplication(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;
int start = 1;
int end = length - 1;
while(end >= start)
{
int middle = ((end - start) >> 1) + start;
int count = countRange(numbers, length, start, middle);
if(end == start)
{
if(count > 1)
return start;
else
break;
}
if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}
int countRange(const int* numbers, int length, int start, int end)
{
if(numbers == nullptr)
return 0;
int count = 0;
for(int i = 0; i < length; i++)
if(numbers[i] >= start && numbers[i] <= end)
++count;
return count;
}
void main()
{
test1();
test2();
test3();
test4();
test5();
test6();
test7();
test8();
test9();
test10();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138794.html
標籤：其他