public class Solution {

public int majorityElement(int[] nums) {

int low = 0;

int high = nums.length - 1;

while (true) {

int index = partition(nums, low, high);

if (index == nums.length / 2)

return nums[index];

else if (index > nums.length / 2)

high = index - 1;

else

low = index + 1;

}

}

private int partition(int[] nums, int low, int high) {

int pivotIdx = (int)(Math.random() * (high - low + 1)) + low;

int pivot = nums[pivotIdx];

nums[pivotIdx] = nums[low];

int lowIdx = low;

int highIdx = high;

while (lowIdx < highIdx) {

while (lowIdx < highIdx && nums[highIdx] >= pivot)

highIdx--;

nums[lowIdx] = nums[highIdx];

while (lowIdx < highIdx && nums[lowIdx] <= pivot)

lowIdx++;

nums[highIdx] = nums[lowIdx];

}

nums[lowIdx] = pivot;

return lowIdx;

}

}