给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。
请注意,它是排序后的第k小元素,而不是第k个元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。
第一行为k的值和矩阵的n的值
后续为n*n矩阵的数字,以空格分割
矩阵中第k小的元素
8 3 1 5 9 10 11 13 12 13 15
13
public static void solve(int[][] arr,int k) { int[] pos=new int[arr.length]; int tmp=0; for(int i=0;i<k;i++) { tmp=Integer.MAX_VALUE; int index=0; for(int j=0;j<arr.length;j++) { if(pos[j]<arr.length&&arr[j][pos[j]]<tmp) { tmp=arr[j][pos[j]]; index=j; } } pos[index]++; } System.out.println(tmp); }
import java.util.Arrays; import java.util.Scanner; public class Main { /** * 运行时间:64ms * * 占用内存:10520k * */ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int k = scanner.nextInt(); int n = scanner.nextInt(); int[] record = new int[n * n]; for (int i = 0; i < n * n; i++) { record[i]=scanner.nextInt(); } Arrays.sort(record); System.out.println(record[k-1]); } }
import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int k = sc.nextInt(); int n = sc.nextInt(); int x; int[] arr = new int[n * n]; for(int i = 0;i < n * n;i++){ x = sc.nextInt(); arr[i] = x; } Arrays.sort(arr); System.out.println(arr[k-1]); } }sort:又不是不能用🤣