Beating 100% of java submissions with quick-select method


  • 0
    M
    public class Solution {
    public List<Integer> majorityElement(int[] a) {
        List<Integer> res = new ArrayList<Integer>();
        sort(a, 0, a.length - 1, res);
        return res;
    }
    
    private void sort(int[] a, int s, int e, List<Integer> res) {
        if (e < s) return;
        int p = a[s];
        int i = s; int j = e; int k = s;
        while (i <= j) {
            if (a[i] < p) {
                int tmp = a[k]; a[k] = a[i]; a[i] = tmp;
                k++; i++;
            } else if (a[i] > p) {
                int tmp = a[j]; a[j] = a[i]; a[i] = tmp;
                j--;
            } else {
                i++;
            }
        }        
        
        if (i - k > a.length / 3) {
            res.add(p);
        }
        
        if (k - s > a.length / 3) {
            sort(a, s, k - 1, res);
        }
        
        if (e + 1 - i > a.length / 3) {
            sort(a, i, e, res);
        }
    }
    

    }


  • 0
    D
    This post is deleted!

  • 0
    M

    Array.sort time complexity is O (N log N), where the Quick Select time complexity is O (N)


Log in to reply
 

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