Share my AC Java Solution


  • 0
    S

    The idea is, each time, we compare the head with the mid and get the larger one as new head(include the edge). For example :
    5 6 1 | 2 3 4
    Since 5 > 2, we get -> 5 6 1
    5 | 6 1
    Since 6 > 5, we get -> 6 1
    If it is a rotate array, the right one must be the smallest number
    If not, we just need return num[0]

    public class Solution {
        public int findMin(int[] num) {
            if(num.length == 1) {
                return num[0];
            }
            int left = 0; int right = num.length-1; int mid = (left + right + 1) / 2;
            while(left < right && mid != right) {
                int leftNum = num[left];
                int rightNum = num[right];
                int midNum = num[mid];
                if(leftNum > midNum) {
                    right = mid;
                    mid = (left + right + 1) / 2;
                } else {
                    left = mid;
                    mid = (left + right + 1) / 2;
                }
            }
            if(num[left] < num[right]) {
                return num[0];
            } else {
                return num[right];
            }
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.