面试经典 150 题 （五）

快排

class Solution {
    public int majorityElement(int[] nums) {
        QuickSort(nums, 0, nums.length - 1);
        return nums[nums.length / 2];
    }

    int partition(int[] nums, int left, int right) {
        int l = left;
        int r = right;
        int pivot = nums[l];
        while (l < r) {
            while (l < r && pivot <= nums[r])
                r--;
            nums[l] = nums[r];
            while (l < r && pivot >= nums[l])
                l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }

    void QuickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivotPos = partition(nums, left, right);
            QuickSort(nums, left, pivotPos - 1);
            QuickSort(nums, pivotPos + 1, right);
        }
    }
}

哈希表

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> numsMap = nums2map(nums);
        Set<Map.Entry<Integer, Integer>> numSet = numsMap.entrySet();
        Map.Entry<Integer, Integer> majorityEnrty = null;
        for (Map.Entry<Integer, Integer> entry: numSet){
            if(majorityEnrty == null || majorityEnrty.getValue() < entry.getValue()){
                majorityEnrty = entry;
            }
        }
        return majorityEnrty.getKey();
    }
    public Map<Integer, Integer>  nums2map(int[] nums){
        Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();
        for(int num : nums){
            if (!numMap.containsKey(num)){
                numMap.put(num, 1);
            }else{
                numMap.put(num, numMap.get(num) + 1);
            }
        }
        return numMap;
    }
}