Stop wasting your time. It most likely has to be O(n).


  • 2
    D

    There is no faster way than O(n) to solve an input like "1 1 1 1 1 0 1 1 1 1 1 1 1 1". Binary search won't work in this case as your nums[start] == nums[mid] == nums[end], which half would you discard then? In other words, you have to examine all elements. With that being said, this is probably the only way to solve it. Run time: 6ms. Not bad at all.

    
    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int min = nums[0];
            for (int val : nums)
            {
                if (min > val)
                {
                    min = val;
                }
            }
            
            return min;
        }
    };
    

  • 0
    U

    Interesting post


  • 3
    C

    This is the worst case, in terms of average, binary search is still better


  • 0
    S

    I got 1ms with line comparing O(n).
    And binary search 1ms too.
    May be this is time to make unit of computing time smaller~~


Log in to reply
 

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