Another solution based on Partition from QuickSort


  • 0
    H
    #code
    public class Solution {
        public int majorityElement(int[] nums) {
            int mid = nums.length >> 1;
            int left = 0;
            int right = nums.length - 1;
            int pivot = nums[right];
            int index = partition(nums, left, right, pivot);
            while (index != mid) {
                if (index > mid) {
                    right = index - 1;
                } else {
                    left = index + 1;
                }
                pivot = nums[right];
                index = partition(nums, left, right, pivot);
            }
            return nums[index];
        }
        private int partition(int[] nums, int left, int right, int pivot) {
            int l = left - 1;
            int r = right;
            while (true) {
                while (l < nums.length - 1 && nums[++l] < pivot);
                while (r > 0 && nums[--r] > pivot);
                if (l >= r) {
                    break;
                }
                swap(nums, l, r);
            }
            swap(nums, l, right);
            return l;
        }
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

Log in to reply
 

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