JZ11 旋转数组的最小数字_学习

JZ11 旋转数组的最小数字

创始人

2024-05-20 10:48:32

【答案解析】：暴力破解：遍历数组找出最小值即可更优思想：采用二分查找，这个题主要分析三种旋转情况 [1, 2, 3, 4, 5]，使用中间值与右端进行比较。 1. 中间大于右边 [3, 4, 5, 1, 2]，这种情况下，最小数一定在右边；则left = middle + 1 2. 中间等于右边 [1, 0, 1, 1, 1], 这个是[0, 1, 1, 1, 1] 旋转过来的，这时候需要缩小范围 right--;，注意不能是 left++，因为是非降序数组，所以要缩小右边范围，把较小值向右推，符合我们的判断规则。 3. 中间小于右边 [5, 1, 2, 3, 4], 这种情况下，最小数字则在左半边；则right = middle 本人代码：

/*** * @param rotateArray int整型一维数组 * @param rotateArrayLen int rotateArray数组长度* @return int整型*/
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) 
{// write code hereif (rotateArrayLen == 0)                     //考虑特殊情况{return 0;}else{int left = 0;int right = rotateArrayLen - 1;while (left < right){int mid = (left + right) / 2;                             //二分查找if (rotateArray[mid] > rotateArray[right]){left = mid + 1;}else if (rotateArray[mid] < rotateArray[right]){right = mid;}else{right--;}}return rotateArray[left];}
}

标准答案：

int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
if (rotateArrayLen == 0) return 0;
int left = 0, right = rotateArrayLen - 1, mid;
if (rotateArray[right] > rotateArray[left]) return rotateArray[0];
while(left < right) {
mid = left + (right - left) / 2;
if (rotateArray[mid] > rotateArray[right]) left=mid+1;
else if (rotateArray[mid] == rotateArray[right]) right--;
else right = mid;
}
return rotateArray[left];
}

上一篇：Java基础之异常处理

下一篇：4、因果法

JZ11 旋转数组的最小数字

相关内容

热门资讯