A possible answer with O(lg N)


  • 0
    E
    class Solution {
    public:
        int findMin(vector<int> &num) {
            int head = 0;
            int tail = num.size() - 1;
            while(head < tail)
            {
                if(num[head] == num[tail])
                {
                    --tail;
                    continue;
                }
                if(num[head] < num[tail])
                    break;
                int body = (head + tail) / 2;
                if(num[head] <= num[body])
                    head = body + 1;
                else
                    tail = body;
            }
            return num[head];
        }
    };

  • 1
    Z

    The worst-case time complexity of the above solution is still O(n). Consider the example where there is exactly one minimum as the second element of the array and all the other elements are the same and strictly greater than the minimum, such as

    {2, 1, 2, 2, 2, ...}


  • 0
    E

    yeah, you are right! thanks!


Log in to reply
 

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