网站设置评价,百度知道官网手机版,四川高端网站建设,天津电商网站开发题目描述 把一个数组最开始的若干个元素搬到数组的末尾#xff0c;我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转#xff0c;输出旋转数组的最小元素。 解题思路 将旋转数组对半分可以得到一个包含最小元素的新旋转数组#xff0c;以及一个非递减排序的数组。新… 题目描述 把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转输出旋转数组的最小元素。 解题思路 将旋转数组对半分可以得到一个包含最小元素的新旋转数组以及一个非递减排序的数组。新的旋转数组的数组元素是原数组的一半从而将问题规模减少了一半这种折半性质的算法的时间复杂度为 O(logN)为了方便这里将 log2N 写为 logN。 此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。 通过修改二分查找算法进行求解 当 nums[mid] nums[high] 时表示 [mid, high] 区间内的数组是非递减数组[low, mid] 区间内的数组是旋转数组此时令 high mid否则 [mid 1, high] 区间内的数组是旋转数组令 low mid 1。public int minNumberInRotateArray(int[] arr) {if (arr.length 0) {return 0;}int low 0;int high arr.length - 1;while (low high) {int mid low (high - low) / 2;// 注意此处比较的是后半段if (arr[mid] arr[high]) { high mid;} else {low mid 1;}}return arr[low];
} 如果数组元素允许重复会出现一个特殊的情况nums[low] nums[mid] nums[high]此时无法确定解在哪个区间需要切换到顺序查找。例如对于数组 {1, 1, 1, 0, 1}low、mid 和 high 指向的数都为 1此时无法知道最小数字 0 在哪个区间。 public int minNumberInRotateArray(int[] arr) {if (arr.length 0) {return 0;}int low 0;int high arr.length - 1;while (low high) {int mid low (high - low) / 2;if (arr[low] arr[mid] arr[mid] arr[high]) {return minNumber(arr, low, high);} else if (arr[mid] arr[high]) {high mid;} else {low mid 1;}}return arr[low];
}private int minNumber(int[] arr, int low, int high) {for (int i low; i high; i) {if (arr[i] arr[i 1]) {return arr[i 1];}}return arr[low];
} 参考 CyC2018 转载于:https://www.cnblogs.com/yueshutong/p/11571495.html
