旋转数组中的最小数字 • Mility

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组。

注意：旋转数组中包含两递增排序的子数组，有阴影背景的是第二个子数组。（a）把P1指向数组的第一个数字，P2指向数组的最后一个数字。由于P1和P2中间的数字5大于P1指向的数字，中间的数字在第一个子数组中。下一步把P1指向中间的数字。（b）P1和P2中间的数字1小于P2指向的数字，中间的数字在第二个子数组中。下一步把P2指向中间的数字。（c）P1和P2指向两个相邻的数字，则P2指向的是数组中的最小数字。

int Min(int * numbers, int length){
   if(numbers == NULL || length <= 0)
      throw new std::exception("Invalid parameters");
    
    int index1 = 0;
    int index2 = length -1;
    int indexMid = index1;
    while(numbers[index1]>=numbers[index2]){
      if(index2 - index1 == 1){
        indexMid = index2;
        break;
      }
      indexMid = (index2 + index1) / 2;
      if(numbers[indexMid] >= numbers[index1])
        index1 = indexMid;
      else if(numbers[indexMid] <= numbers[index2])
        index2 = indexMid;
    }
    return numbers[indexMid];
}

当两个指针指向的数字及它们中间的数字三者相同的时候，我们无法判断中间的数字是位于前面的子数组中还是后面的子数组中，也就无法移动两个指针来缩小查找的范围。此时，我们不得不采用顺序查找的方法。
在把问题分析清楚形成清晰的思路之后，我们可以把前面的代码修改为：

/*
 * MInNumberInRotatedArray.cpp
 *
 *  Created on: 2016年7月22日
 *      Author: mility
 */
// MinNumberInRotatedArray.cpp : Defines the entry point for the console application.
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者：何海涛
#include <stdexcept>
#include <stdio.h>

using namespace std;

int MinInOrder(int* numbers, int index1, int index2);

int Min(int* numbers, int length) {
	if (numbers == NULL || length <= 0)
		throw new std::exception();

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

// ====================测试代码====================
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 == NULL)
			printf("Test passed.\n");
		else
			printf("Test failed.\n");
	}
}

int main(void) {
	// 典型输入，单调升序的数组的一个旋转
	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);

	// 输入NULL
	Test(NULL, 0, 0);

	return 0;

}

且控制台的输出为：

4 5 1 2 	passed  
4 5 1 1 2 	passed  
4 5 1 2 2 	passed  
0 1 1 1 	passed  
2 3 4 5 	passed  
passed  
Test passed.  

Back to the top!