Dose this one is available during interview?


  • 2
    Z
    public int majorityElement(int[] num) {
       	Arrays.sort(num);
    	int mid=(num.length-1)/2;
    	return num[mid];
        
    }

  • 4
    S

    How can Arrays.sort be used during interview?
    By the way, sort() use O(nlgn), but a better solution just uses O(n)

    int majorityElement(vector<int> &num) {
        if(!num.size())
            return 0;
        if(num.size()<=2)
            return num[0];
        int a(0),base(0);
        for(int number : num)
        {
            if(a == 0||number == base)
            {
                base = number;
                ++a;
            }
            else
            {
                --a;
            }
        }
        return base;
    }

  • 0
    S

    But quick sort does not use extra space while the O(n) solution as far as I can figure out uses O(n) space as well as it uses the hash table.


  • 0
    S

    Just look my c++ solution above, O(1) space, no hash table, O(n) time complex


  • 0
    G

    I use library functions unless the interviewer explicitly tells me not to. Even you can't use Arrays.sort, you can write a sorting algorithm from your memory first.


  • 1
    S

    I would say it is a quite interesting answer. You definitely can mention to your interviewer but point out the time complexity. However, the interviewer would not require you to write a code for it.


Log in to reply
 

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