Leetcode 154) Find Minimum in Rotated Sorted Array2

17 Sep 2021 in Algorithms

My solution

• 오 hard 인데 그래도 세번 도전만에 푼게 대견하다.. 이렇게 성장하는거겟지………… 아닌가…

class Solution {
    public int findMin(int[] nums) {
        //this is very simillar to the previous one, 
        // the starategy from previous question can be used with comparing neibors' value.
        //meaning , the while loop is going to run when there are at least 3 elements present.
        // becasue there could be the case where [4,5,6,7,0,1,4], and don't know which half to go!
        int left= 0;
        int right= nums.length-1;

        while(left+1<right){
            int mid = left + (right-left)/2;
            // when it is vague  
            if(nums[left] == nums[right]){
                if(nums[mid]==nums[right]){
                    //if mid is also the same?
                    //n 탐색을 쓸 수 밖에 없는거같은데?
                    while(right>1 && nums[mid]==nums[right]){
                        right--;
                    }
                    //중복 없앨 수 있을 때 까지 최대한 없애
                    //while 문 나온 후에도 left가 boundary안이길 바라니까 이렇게 쓴다.
                    while(left<right-1 && nums[mid]==nums[left]){
                        left++;
                    }

                }else{
                    if(nums[mid]>nums[left]){
                        // 11123401111
                        left=mid;
                    }else{
                        //444000234444
                        right=mid;
                    }
                }
            }else{
                //nums[left]!=nums[right]
                //When there is no rotation happened
                if(nums[left]<=nums[mid] && nums[mid]<=nums[right]){
                    return nums[left];
                }else if(nums[left]<=nums[mid]){
                    //when nums[mid]>nums[right]
                    left=mid;
                }else if(nums[right]>=nums[mid]){
                    //when nums[left] > nums[mid]
                    right= mid;
                }

            }
        }
        //원소 두개..
        if(nums[left] < nums[right]){
            return nums[left];
        }else{
            return nums[right];
        }
    }
}

Other Answer

• ㅋㅋㅋ 정답 보니까 현타 ㅋㅋㅋ
• 어떻게 줄일 수 있는지 이번주 일요일에 탐구하기

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int low = 0;
        int high = n - 1;
        while(low < high){
            int mid = (low + high) / 2;
            if(nums[mid] < nums[high]){
                high = mid;
            }else if(nums[mid] > nums[high]){
                low = mid + 1;
            }else{
                high--;
            }
        }
        return nums[high];
    }
}