题解 | #寻找第K大#

	
	

		
		

			
			

				执行结果：
				

					通过
				

				

					显示详情
				

			

			

				
				

					
					

						添加备注
					

				

			

		

		

			执行用时：1 ms, 在所有 Java 提交中击败了98.38%的用户
		

		

			内存消耗：41.3 MB, 在所有 Java 提交中击败了75.02%的用户
		

		

			通过测试用例：32 / 32
		

	




	

public static int findKth(int[] a, int n, int K) {
        // write code here
        int cnt = 0;
        for (int i = (n - 1) / 2; i >= 0; i--) {
            adjustHeap(a, i, n);
        }
        for (int i = n - 1; i >= 0; i--) {
            int tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            cnt++;
            if (cnt == K) {
                return a[n - K];
            }
            adjustHeap(a, 0, i);
        }
        return 0;
    }

    public static void adjustHeap(int[] array, int parent, int length) {
        int lChild = 2 * parent + 1;
        if (lChild < length) {
            int rChild = lChild + 1;
            if (rChild < length && array[rChild] > array[lChild]) {
                lChild++;
            }
            if (array[parent] >= array[lChild]) {
                return;
            }
            int tmp = array[parent];
            array[parent] = array[lChild];
            array[lChild] = tmp;
            adjustHeap(array, lChild, length);
        }
    }