Solution by xuyangit


  • 1
    X

    Approach #1 Brute Force [Accepted]

    Intuition

    Simply iterate the given array to find the minimum number.

    Algorithm

    We use a variable to store the minimum value, which is set to the max value of integer initially. Then we compare this number with every number in the given array to get the minimum value.

    Java

    public class Solution {
        public int findMin(int[] nums) {
            int minNum = Integer.MAX_VALUE;
            for(int num : nums) {
                minNum = Math.min(minNum, num);
            }
            return minNum;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.
    • Space complexity : $$O(1)$$.

    The comparison is done for exactly $$n$$ times, so the time complexity is $$O(n)$$. The space complexity is apparent.


    Approach #2 Binary Search [Accepted]

    Algorithm

    Suppose we have an array denoted as $$A_n=[a_1,a_2,\ldots,a_n]$$. An easy observation is that, if the central number (i.e., the $$\lfloor\frac{n}{2}\rfloor$$th number) is bigger than the last number (i.e., $$a_n$$), then the minimum number can only appear in the right part of this central number. In this case, we can quickly abandon the left part of $$A_n$$ including the central number. Notice there are not duplicate numbers in this problem, so the other case is that the central number is smaller than the last number. Then the numbers after the central number must be bigger than it, which means they can be discarded. Notice that the remaining sequence is still a rotated array so the above observation always holds when we search. Recursively we can get the final answer.

    Java

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

    Complexity Analysis

    • Time complexity : $$O(lgn)$$. In each iteration we will discard half of the numbers, so the time complexity is $$O(lgn)$$

    • Space complexity : $$O(1)$$. Only two variables are used here.


Log in to reply
 

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