给别人做网站的销售叫什么软件,怎么样把自己的产品网上推广,wordpress 简约,大淘客网站怎样做百度推广本文正在参加「Java主题月 - Java 刷题打卡」#xff0c;详情查看 活动链接
题目
给你一个二维矩阵 matrix 和一个整数 k #xff0c;矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 i a m 且 0 j b n 的元素…本文正在参加「Java主题月 - Java 刷题打卡」详情查看 活动链接
题目
给你一个二维矩阵 matrix 和一个整数 k 矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 i a m 且 0 j b n 的元素 matrix[i][j]下标从 0 开始计数执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值k 的值从 1 开始计数。
示例 1
输入matrix [[5,2],[1,6]], k 1 输出7 解释坐标 (0,1) 的值是 5 XOR 2 7 为最大的值。
示例 2
输入matrix [[5,2],[1,6]], k 2 输出5 解释坐标 (0,0) 的值是 5 5 为第 2 大的值。
示例 3
输入matrix [[5,2],[1,6]], k 3 输出4 解释坐标 (1,0) 的值是 5 XOR 1 4 为第 3 大的值。
示例 4
输入matrix [[5,2],[1,6]], k 4 输出0 解释坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 0 为第 4 大的值。
解题思路
维护一个前缀异或数组sum[i][j],代表以ij为右下角的矩形的异或结果因此sum[i][j]的值可以从sum[i-1][j]sum[i][j-1]sum[i-1][j-1]的结果中推出来递推式为sum[i][j]sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^matrix[i-1][j-1]; 2. 将所有异或的数组进行一次排序就能得出第k大的元素了
代码
class Solution {public int kthLargestValue(int[][] matrix, int k) {ArrayListInteger list new ArrayList();int nmatrix.length,mmatrix[0].length,res0;int[][] sum new int[n 1][m 1];for (int i 1; i n; i) {for (int j 1; j m; j) {sum[i][j]sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^matrix[i-1][j-1];list.add(sum[i][j]);}}Collections.sort(list);return list.get(list.size()-k);}
}结果 使用优先队列进行排序 public int kthLargestValue(int[][] matrix, int k) {PriorityQueueInteger priorityQueuenew PriorityQueue();int nmatrix.length,mmatrix[0].length,res0;int[][] sum new int[n 1][m 1];for (int i 1; i n; i) {for (int j 1; j m; j) {sum[i][j]sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^matrix[i-1][j-1];if(priorityQueue.size()k){priorityQueue.add(sum[i][j]);}else if(priorityQueue.peek()sum[i][j]){priorityQueue.poll();priorityQueue.add(sum[i][j]);}}}return priorityQueue.peek();}结果
