题解 | #矩阵第K小#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型ArrayList<ArrayList<>> 
     * @param k int整型 
     * @return int整型
     */
    
    /**********************************************************************************/
    // 快排
    /*
    public int KthinMatrix (ArrayList<ArrayList<Integer>> matrix, int k) {
        // write code here
        int n = matrix.size();
        int[] nums = new int[n * n];
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                nums[index] = matrix.get(i).get(j);
                index++;
            }
        }
        quickSort(nums, 0, nums.length - 1);
        return nums[k - 1];
    }
    
    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        int val = nums[end];
        while (p < r) {
            if (nums[p] < val) {
                int swap = nums[p];
                nums[p] = nums[l + 1];
                nums[l + 1] = swap;
                p++;
                l++;
            }
            else if (nums[p] > val) {
                int swap = nums[p];
                nums[p] = nums[r - 1];
                nums[r - 1] = swap;
                r--;
            }
            else {
                p++;
            }
        }
        quickSort(nums, start, l);
        quickSort(nums, r, end);
    }
    */
    
    /**********************************************************************************/
    // 堆排
    public int KthinMatrix (ArrayList<ArrayList<Integer>> matrix, int k) {
        int n = matrix.size();
        int[] nums = new int[n * n];
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                nums[index] = matrix.get(i).get(j);
                index++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums, i);
        }
        int heapSize = nums.length;
        swap(nums, 0, --heapSize);
        while (nums.length - heapSize != k) {
            heapify(nums, 0, heapSize);
            swap(nums, 0, --heapSize);
        }
        return nums[nums.length - k];
    }
    
    public void heapSort(int[] nums) {
        if (0 == nums.length || 1 == nums.length) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums, i);
        }
        int heapSize = nums.length;
        swap(nums, 0, --heapSize);
        while (heapSize > 0) {
            heapify(nums, 0, heapSize);
            swap(nums, 0, --heapSize);
        }
    }

    public void heapInsert(int[] nums, int index) {
        while (nums[index] < nums[(index - 1) / 2]) {
            swap(nums, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public void heapify(int[] nums, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int smallest = left + 1 < heapSize && nums[left + 1] < nums[left] ? left + 1 : left;
            smallest = nums[smallest] < nums[index] ? smallest : index;
            if (smallest == index) {
                break;
            }
            swap(nums, smallest, index);
            index = smallest;
            left = index * 2 + 1;
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}