题目
该系列文章题目和思路均参考自:《剑指Offer》
解法
思路1:求解一个数组中的最小元素,很容易想到进行遍历即可,时间复杂度为O(n)。但这种方式没有用到题目中给的数组旋转的特点。
思路2:类似于二分查找法。使用两个指针分别指向数组头(p1)和尾(p2),然后查找到两个指针中间的元素,如果中间的元素位于前面递增的子数组中,那么它应该大于等于p1指向的元素,那么数组中最小的元素在后半部分。这样就可以将p1移动到中间元素的位置,在进行查找。
类似的如果中间的元素位于后面的递增子数组中,那么它应该小于或等于p2指向的元素,此时数组中最小的元素应该位于前半部分。这样就可以将p2移动到中间元素的位置在进行查找。
根据以上思路,p1指针总是指向前面递增子数组的元素,p2指针总是指向后面递增子数组的元素,最后p1将指向前面递增子数组的最后一个元素,p2将指向后面递增子数组的第一个元素。p1和p2即相邻,此时p2指向的元素即为数组中最小的元素。
特殊的:如果把排序数组的前0个元素搬到最后面,即排序数组本身,这仍然是一个旋转。因此在上述的思路中,将中间节点元素的指针初始化为p1,即如果array[p1]>array[p2]不成立(数组有序),则直接返回数组中第一个元素即为最小的元素。
更特殊的:考虑如下两个旋转后的数组,第一个数字,最后一个数字和中间的数字都是1,无法使用上述的条件进行查找,此时就只能使用顺序查找的方法对数组中最小的元素进行查找了。
代码如下:
/**
* 面试题11:旋转数组中最小的数字
*/
public class FindMinNumber {
public static int findMinNumberInOrder(int[] array) {
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] < min) {
min = array[i];
}
}
return min;
}
public static void findMinNumber(int[] array) {
if (array.length <= 0)
return;
int p1 = 0;
int p2 = array.length - 1;
int mid = p1;
while (array[p1] >= array[p2]) {
if (p2 - p1 == 1) {
System.out.println(array[p2]);
break;
}
mid = (p1+p2) / 2;
// 针对p1,p2和mid指向的元素相同时,只能使用顺序查找的方法
if (array[p1] == array[p2] && array[p1] == array[mid]) {
System.out.println(findMinNumberInOrder(array));
break;
}
if (array[mid] >= array[p1]) {
p1 = mid;
} else if (array[mid] <= array[p2]) {
p2 = mid;
}
}
}
public static void main(String[] args) {
int[] array1 = {3,4,5,1,2};
int[] array2 = {1,0,1,1,1};
int[] array3 = {1,1,1,0,1};
findMinNumber(array1);
findMinNumber(array2);
findMinNumber(array3);
}
}
最后
以上就是忧心枫叶最近收集整理的关于面试题11:旋转数组的最小数字的全部内容,更多相关面试题11:旋转数组内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复