題目：把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，輸入一個遞增排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，例如，陣列{3， 4， 5， 1， 2}為{1， 2， 3， 4， 5}的一個旋轉，該數字的最小值為1，
測驗用例：
- 功能測驗（輸入的陣列是升序排序陣列的一個旋轉，陣列中有重復數字或者沒有重復數字），
- 邊界值測驗（輸入的陣列是一個升序排序的陣列，只包含一個數字的陣列），
- 特殊輸入測驗（輸入nullptr指標），
測驗代碼：
void Test(int* numbers, int length, int expected)
{
int result = 0;
try
{
result = Min(numbers, length);
for(int i = 0; i < length; ++i)
printf("%d ", numbers[i]);
if(result == expected)
printf("\tpassed\n");
else
printf("\tfailed\n");
}
catch (...)
{
if(numbers == nullptr)
printf("Test passed.\n");
else
printf("Test failed.\n");
}
}
本題考點：
- 考查應聘者對二分查找的理解，本題變換了二分查找的條件，輸入的陣列不是排序的，而是排序陣列的一個旋轉，這要求我們對二分查找的程序有深刻的理解，
- 考查應聘者的溝通能力和學習能力，本題面試官提出了一個新的概念：陣列的旋轉，我們要在很短的時間內學習、理解這個新概念，在面試程序中，如果面試官提出新的概念，那么我們可以主動和面試官溝通，多問幾個問題，把概念搞清楚，
- 考查應聘者思維的全面性，排序陣列本身是陣列旋轉的一個特例，另外，我們要考慮到陣列中有相同數字的特例，如果不能很好地處理這些特例，就很難寫出讓面試官滿意的完美代碼，
實作代碼：
#include <cstdio>
#include <stdexcept>
int MinInOrder(int* numbers, int index1, int index2);
int Min(int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
throw std::logic_error("Invalid parameters");
int index1 = 0;
int index2 = length - 1;
int indexMid = index1;
while(numbers[index1] >= numbers[index2])
{
// 如果index1和index2指向相鄰的兩個數，
// 則index1指向第一個遞增子陣列的最后一個數字，
// index2指向第二個子陣列的第一個數字，也就是陣列中的最小數字
if(index2 - index1 == 1)
{
indexMid = index2;
break;
}
// 如果下標為index1、index2和indexMid指向的三個數字相等，
// 則只能順序查找
indexMid = (index1 + index2) / 2;
if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
return MinInOrder(numbers, index1, index2);
// 縮小查找范圍
if(numbers[indexMid] >= numbers[index1])
index1 = indexMid;
else if(numbers[indexMid] <= numbers[index2])
index2 = indexMid;
}
return numbers[indexMid];
}
int MinInOrder(int* numbers, int index1, int index2)
{
int result = numbers[index1];
for(int i = index1 + 1; i <= index2; ++i)
{
if(result > numbers[i])
result = numbers[i];
}
return result;
}
int main(int argc, char* argv[])
{
// 典型輸入，單調升序的陣列的一個旋轉
int array1[] = { 3, 4, 5, 1, 2 };
Test(array1, sizeof(array1) / sizeof(int), 1);
// 有重復數字，并且重復的數字剛好的最小的數字
int array2[] = { 3, 4, 5, 1, 1, 2 };
Test(array2, sizeof(array2) / sizeof(int), 1);
// 有重復數字，但重復的數字不是第一個數字和最后一個數字
int array3[] = { 3, 4, 5, 1, 2, 2 };
Test(array3, sizeof(array3) / sizeof(int), 1);
// 有重復的數字，并且重復的數字剛好是第一個數字和最后一個數字
int array4[] = { 1, 0, 1, 1, 1 };
Test(array4, sizeof(array4) / sizeof(int), 0);
// 單調升序陣列，旋轉0個元素，也就是單調升序陣列本身
int array5[] = { 1, 2, 3, 4, 5 };
Test(array5, sizeof(array5) / sizeof(int), 1);
// 陣列中只有一個數字
int array6[] = { 2 };
Test(array6, sizeof(array6) / sizeof(int), 2);
// 輸入nullptr
Test(nullptr, 0, 0);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139455.html
標籤：其他
下一篇：C++分治策略實作線性時間選擇