Leetcode 1738

这是Leetcode 5.19的题目 1738. 找出第 K 大的异或坐标值，是215. 数组中的第K个最大元素的二维异或版本 215回顾

第一种方法，用前缀异或 + PriorityQueue , Java是用最小堆实现pq

public int kthLargestValue(int[][] matrix, int k) {
	    int m = mat.length , n = mat[0].length;
        int[][] pre = new int[m + 1][n + 1];
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 1; i <= m ; i++) {
            for (int j = 1; j <= n ; j++) {
                //二维数组的前缀异或
                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ mat[i - 1][j - 1];
                if (pq.size() < k){
                    pq.add(pre[i][j]);
                }else {
                    if (pre[i][j] > pq.peek()){
                        //大于size直接去掉
                        //直到剩下K个值
                        //pq.peek()即是题目想要的第K大
                        pq.poll();
                        pq.add(pre[i][j]);
                    }
                }
            }
        }
        return pq.peek();
    }
}

第二种方法，用前缀异或 + 排序

public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length , n = matrix[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        List<Integer> list = new ArrayList<>();

        /** 二维数组的前缀异或 */
        for (int i = 1; i <= m ; i++) {
            for (int j = 1; j <= n ; j++) {
                prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ prefix[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                list.add(prefix[i][j]);
            }
        }

    	//这里用了Collections.sort(List , new Comparator(){
    	//   @Override
    	//	public int compare(Object o1 , Object o2)
		//});
    	//当o2 - o1 > 0 ,即把大的值放前面
    	//降序排列
        Collections.sort(list, ((o1, o2) -> o2 - o1));

        return list.get(k - 1);
}