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

• ``````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) {
}
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.

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