Divide and conquer solution derived from three-way quicksort


  • 0
    P
    public class Solution {
        public int majorityElement(int[] nums) {
            int lt = 0, gt = nums.length-1;
            int v = nums[0];
            int i = 0;
            while (i <= gt) {
                if (nums[i] < v) {
                    int temp = nums[lt];
                    nums[lt++] = nums[i];
                    nums[i++] = temp;
                }
                else if (nums[i] > v) {
                    int temp = nums[i];
                    nums[i] = nums[gt];
                    nums[gt--] = temp;
                }
                else   i++;
            }
    
            if (nums[nums.length/2] < v) return majorityElement(Arrays.copyOfRange(nums, 0, nums.length/2));
            if (nums[nums.length/2] > v) return majorityElement(Arrays.copyOfRange(nums, nums.length/2, nums.length));
            return v;
        }
    }
    

Log in to reply
 

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