Is this a cheating solution ??


  • -18
    K

    I got accepted by two lines of code...

    public int findMin(int[] num) 
    {
        Arrays.sort(num);
        
        return num[0];
    }

  • 1
    Z

    you should know the time complexity of Arrays.sort(num) is O(N*lgN);


  • 0
    K

    We have to find a O(N) solution, right?

    I have another solution, it looks bad but it solves the problem in O(N).

    public int findMin(int[] num) 
    {
        boolean flag = false;
        
        for (int i = 0; i < num.length; i++)
        {
            if (num[i % num.length] != num[(i+1) % num.length])
            {
                flag = true;
            }
        }
        
        int result = num[0];
        
        if (flag)
        {
            for (int i = 0; i < num.length; i++)
            {
                if (num[i % num.length] > num[(i+1) % num.length])
                {
                    result = num[(i+1) % num.length];
                    break;
                }
            }
        }
        
        return result;
    }

  • 0
    Z

    if u use
    for (int i = 0; i < num.length; i++)
    u can find min in one pass.

    but u didn't use the Sorted property of array.
    so the best and worst time consuming for your code is always O(N).


  • -15
    T

    Very simple accepted answer.

      int min = num[0];
        for(int i = 1; i< num.length;i++)
        {
            if(num[i] < min)
            {
                min = num[i];
            }
        }
        
        return min;

  • 0
    C

    Yes, I used the same approach, and got accepted. Seems no need to do recursion, nor binary search...


  • 0
    C

    Yes, I used the same approach, and got accepted. Seems no need to do recursion, nor binary search...


  • 0
    D

    This is clearly an average O(n) solution. Using binary search gives you O(log(n)) average solution with worst case O(n). (when whole array contains same number)


  • -2
    Z

    there is other simple code solution, we can return result when we find it.

        public int findMin(int[] num) {
            int tail = num[num.length - 1];
            for (int i = 0; i < num.length - 1; i++) {
                if (num[i] < tail)
                    return num[i];
            }
            return tail;
        }

  • 0
    H

    This will destroy the original vector.


Log in to reply
 

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