题解 | #旋转排列之找出最矮的牛# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param heights int整型一维数组
     * @return int整型
     */
    public int findMin (int[] heights) {
        // write code here
        int l = 0, r = heights.length - 1;
        if (heights[r] <= heights[l]) {
            return heights[r];
        }

        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (heights[mid] < heights[r]) {
                l = mid + 1;
            } else if (heights[mid] > heights[r]) {
                r = mid;
            } else {
                l += 1;
            }
        }
        return heights[l - 1];
    }
}

编程语言是Java。

该题考察的知识点是二分查找。

代码的文字解释如下：

1. 初始化两个指针l和r，分别指向数组的最左边界和最右边界。
2. 如果数组的最右边界的值小于等于最左边界的值，说明最小值就是最右边界的值，直接返回heights[r]（数组最右边界的值）。
3. 进入循环，当左指针小于右指针时执行以下操作：计算当前区间的中间位置mid，使用(l + r + 1) / 2来避免进入死循环。比较中间位置的元素heights[mid]与最右边界的值heights[r]：如果heights[mid]小于heights[r]，说明最小值在mid的右侧，更新左指针为mid + 1。如果heights[mid]大于heights[r]，说明最小值在mid的左侧或者就是mid，更新右指针为mid。如果heights[mid]等于heights[r]，由于可能存在重复元素，无法确定最小值的位置，将左指针向右移动一位。
4. 循环结束后，返回heights[l - 1]作为最小值。