广西建设厅网站是什么,wordpress主体,做绿色软件的网站知乎,做网站前期创建文件夹题目链接#xff1a;旋转数组的最小数字 文章目录1、题目描述2、题目分析3、代码3.1 Java代码3.2、C代码4、总结1、题目描述
把一个数组最开始的若干个元素搬到数组的末尾#xff0c;我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转#xff0c;输出旋转数组的最小…题目链接旋转数组的最小数字
文章目录1、题目描述2、题目分析3、代码3.1 Java代码3.2、C代码4、总结1、题目描述
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转该数组的最小值为1。 NOTE给出的所有元素都大于0若数组大小为0请返回0。
2、题目分析
从头遍历到尾找到最小值这种low的方法就不说了是个人都会
旋转之后的数组实际上可以划分成两个有序的子数组前面子数组的大小都大于后面子数组中的元素
注意到实际上最小的元素就是两个子数组的分界线。本题目给出的数组一定程度上是排序的因此我们试着用二分查找法寻找这个最小的元素。如下图
思路
1我们用两个指针l_ndex,r_index分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则第一个元素应该是大于最后一个元素的没有重复的元素。 但是如果不是旋转第一个元素肯定小于最后一个元素。
2找到数组的中间元素。
如果中间元素大于第一个元素则中间元素位于前面的递增子数组此时最小元素位于中间元素的后面。我们可以让第一个指针l_index指向中间元素。 移动之后第一个指针仍然位于前面的递增数组中。
如果中间元素小于第一个元素则中间元素位于后面的递增子数组此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。
移动之后第二个指针仍然位于后面的递增数组中。这样可以缩小寻找的范围。
比如当上图的情况那么接下来的下一次循环过后就是下图的样式
3按照以上思路第一个指针l_index总是指向前面递增数组的元素第二个指针r_index总是指向后面递增的数组元素。
最终第一个指针将指向前面数组的最后一个元素第二个指针指向后面数组中的第一个元素。
也就是说他们将指向两个相邻的元素而第二个指针指向的刚好是最小的元素这就是循环的结束条件。
特殊情况
到目前为止以上思路很好的解决了没有重复数字的情况。如果有重复数字情况呢
我们看一组例子10111 和 11 101 都可以看成是非减排序的数组01111的旋转。 这种情况下我们无法继续二分法去解决这道题目。因为在这两个数组中第一个数字最后一个数字中间数字都是1。
第一种情况下中间数字位于后面的子数组绿色第二种情况中间数字位于前面的子数组紫色。
因此当两个指针指向的数字和中间数字相同的时候我们无法确定中间数字1是属于前面的子数组紫色还是属于后面的子数组绿色。
也就无法移动指针来缩小查找的范围。这时只能使用顺序查找法查找。
3、代码
3.1 Java代码
import java.util.ArrayList;
public class Solution {public int minNumberInRotateArray(int [] array) {int size array.length;if(size0)return 0;int l_index0;int r_indexsize-1;int m_index-1;while(array[l_index]array[r_index]){if(r_index - l_index1)break;//当只有两个数时肯定是第二个数是最小数m_indexl_index(r_index-l_index)/2;/* 如果左中右都相等例如101111则无法判断只能按顺序查找 */if(array[l_index]array[m_index] array[m_index]array[r_index])return MinInorder(array,l_index,r_index);if(array[m_index]array[l_index])l_indexm_index;else r_indexm_index;}return array[r_index];}/* 按顺序查找 */int MinInorder(int [] array ,int l,int r){int minarray[l];for(int il;ir;i){if(array[i]min)minarray[i];}return min;}
}3.2、C代码
class Solution {
public:int minNumberInRotateArray(vectorint rotateArray) {int size rotateArray.size();if(size 0)return 0;int l_index 0;int r_index size - 1;int m_index -1;while(rotateArray[l_index]rotateArray[r_index]){if(r_index - l_index 1)break;m_index l_index (r_index-l_index)/2;/* 当左中右都相等时例如101111无法判断只能顺序查找 */if(rotateArray[l_index]rotateArray[m_index] rotateArray[m_index]rotateArray[r_index])return MinInorder(rotateArray,l_index,r_index);if(rotateArray[m_index]rotateArray[l_index])l_index m_index;else if(rotateArray[m_index]rotateArray[r_index])r_index m_index;}return rotateArray[r_index];}int MinInorder(vectorint rotateArray, int index1, int index2){int Min rotateArray[index1];for (int i index1 1; i index2; i){if (rotateArray[i] Min){Min rotateArray[i];}}return Min;}
};
4、总结
注意二分查找的应用与特殊情况的考虑
探讨学习加 qq1126137994 微信liu1126137994
