首页 > 试题广场 >

有序矩阵中第K小的元素

[编程题]有序矩阵中第K小的元素

热度指数：5265 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个 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小的元素

示例1

输入

输出

算法知识视频讲解

Java

牛客196305255号

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);
    }

发表于 2021-03-11 00:38:05 回复(0)

Java

LHC0512

Java解法

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]);
    }
}

发表于 2020-02-29 15:56:18 回复(0)

Java

你的offer对我打了烊

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:又不是不能用🤣

编辑于 2020-02-29 13:40:08 回复(0)