Looks like using 3-way partition to do this to achieve O(1). Looks like very fast, beat 99%?


  • 1
    M
    public List<Integer> majorityElement(int[] nums) {
            if (nums == null || nums.length == 0) return Collections.emptyList();
            int target = nums.length / 3;
            List<Integer> resList = new ArrayList<>();
            threeWayPartition(resList, nums, 0, nums.length - 1, target);
            return resList;
        }
        
        private void threeWayPartition(List<Integer> resList, int[] nums, int left, int right, int target) {
            if (right - left < target) return;
            int lt = left, i = left, gt = right;
            int v = nums[left];
            while (i <= gt) {
                if (nums[i] < v) {
                    swap(nums, i, lt);
                    lt++;
                    i++;
                } else if (nums[i] > v) {
                    swap(nums, i, gt);
                    gt--;
                } else {
                    i++;
                }
            }
            if (i - lt > target) {
                resList.add(nums[lt]);
            }
            threeWayPartition(resList, nums, left, lt - 1, target);
            threeWayPartition(resList, nums, i, right, target);
        }
        
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    

    I use three way partition to do this. Looks like very fast.


Log in to reply
 

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