Leetcode K-Largest Val

215. 数组中的第K个最大元素 , 题目需要在未排序的数组找到第 k 个最大的元素，而且不是第k个不同的元素

先看简单方法，用Java的PriorityQueue来解答，需注意的是PriorityQueue是用小顶堆实现的

public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
		//小顶堆去除元素
        for (int num : nums) {
            pq.offer(num);
            if (pq.size() > k) {
                //因为我们只需要找到第K大的数,超过size直接去除堆顶元素就好
                pq.poll();
            }
        }
        return pq.peek();
    }

亦或者和官方解答一样，用大顶堆实现也可以得出第K大的数

public int findKthLargest(int[] nums, int k) {
            int heapSize = nums.length;
            buildMaxHeap(nums, heapSize);
            for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
                swap(nums, 0, i);
                --heapSize;
                maxHeapify(nums, 0, heapSize);
            }
            return nums[0];
        }

        public void buildMaxHeap(int[] a, int heapSize) {
            for (int i = heapSize / 2; i >= 0; i--) {
                maxHeapify(a, i, heapSize);
            }
        }

        public void maxHeapify(int[] a, int i, int heapSize) {
            int l = i * 2 + 1, r = i * 2 + 2, largest = i;

            if (l < heapSize && a[l] > a[largest]) {
                largest = l;
            }
            if (r < heapSize && a[r] > a[largest]) {
                largest = r;
            }
            if (largest != i) {
                swap(a, i, largest);
                maxHeapify(a, largest, heapSize);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

第三种方法则是用quickSelectionSort 快速选择排序

public int findKthLargest(int[] nums, int k) {
        int low = 0, high = nums.length - 1;
    	//因为无法保证每次pivot都是正中间的索引的
    	//所以我们需要对数组进行一次随机洗牌
        shuffle(nums);
        k = nums.length - k;

        while (low <= high) {
            int p = partition(nums, low, high);
            if (p < k) {
                low = p + 1;
            } else if (p > k) {
                high = p - 1;
            } else {
                return nums[p];
            }
        }
        return -1;
    }

    private int partition(int[] nums, int lo, int hi) {
        if (lo == hi) {
            return lo;
        }
        int pivot = nums[lo];
        // j = hi + 1 因为 while 中会先执行--
        int i = lo, j = hi + 1;

        while (true) {
            // 保证 nums[lo..i] 都小于 pivot
            while (nums[++i] < pivot) {
                if (i == hi) {
                    break;
                }
            }
            // 保证 nums[j..hi] 都大于 pivot
            while (nums[--j] > pivot) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
		   //到了这一步的时候
            //一定会有nums[i] > pivot && nums[j] < pivot
            //因此我们要交换num[i]和num[j]
            //保证nums[low..i] < pivot < nums[j..high]
            swap(nums, i, j);
        }

        //交换pivot
        swap(nums, j, lo);
	   // 现在 nums[low..j-1] < nums[j] < nums[j+1..high]
        return j;
    }

    private void shuffle(int[] nums) {//随机打乱
        int n = nums.length;
        Random ran = new Random();
        for (int i = 0; i < n; i++) {
            int r = i + ran.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }