首页 > 试题广场 >

有序矩阵中第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

输入

输出

算法知识视频讲解

keashem

如果笔试过程中碰到这个题，又没有数据量和时间限制，肯定怎么方便怎么来，直接sort输出3分钟结束战斗；但是刷题时碰到这种特殊的状况的数据，可以往深了想一想，练一练自己的代码能力；下面我提供两个都AC了的方法供大家参考

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt(),n = sc.nextInt();
        int data[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                data[i][j] = sc.nextInt();
            }
        }
        System.out.println(findKthNum(data, k));
        //System.out.println(findKthNum1(data, k));
    }
    //方法1，二分套二分，时间复杂度O(n*logn*logn)
    public static int findKthNum(int[][] matrix, int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int low = matrix[0][0];
        int high = matrix[row - 1][col - 1];
        int mid = 0;
        int count = 0;
        while (low <= high) {
            count = 0;
            mid = low + ((high - low) >> 1);
            for (int[] item : matrix) {
                count += binarySearchCount(item, mid);
            }
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        //返回的low表示满足count >= k的最小的数，这个数就是要找的第k个数
        return low;
    }

    public static int binarySearchCount(int[] data, int k) {
        int begin = 0, end = data.length - 1;
        int mid = 0;
        while (begin <= end) {
            mid = begin + ((end - begin) >> 1);
            if (data[mid] <= k) { //这里要加上等于k的
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        //全大于、全小于k都是begin，正好对应上了
        //这里返回的begin表示<=k的数的个数
        return begin;
    }

    //方法2，快排思想，把二维压成1维，用partion来找第k大的数，复杂度O(n^2)，对比还是第一种方法复杂度低一些
    //但是如果用排序了，对n^2的数据排序复杂度最小为O(n^2*log(n^2))
    public static int findKthNum1(int[][] matrix, int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[] arr = new int[row * col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                arr[i * col + j] = matrix[i][j];
            }
        }
        int begin = 0, end = arr.length - 1;
        int pos;
        while (begin <= end) {
            pos = partition(arr, begin, end);
            if (pos == k - 1) {
                return arr[pos];
            } else if (pos > k - 1) {
                end = pos - 1;
            } else {
                begin = pos + 1;
            }
        }
        return 0;
    }

    public static int partition(int[] arr, int begin, int end) {
        int temp = arr[begin];
        while (begin < end) {
            while (begin < end && arr[end] >= temp) {
                end--;
            }
            swap(arr,begin,end);
            while (begin < end && arr[begin] < temp) {
                begin++;
            }
            swap(arr,begin,end);
        }
        return begin;
    }
    public static void swap(int[]arr,int i,int j){
        if (arr == null || i >= arr.length || j >= arr.length || i < 0 || j < 0) {
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

编辑于 2019-08-06 13:06:47 回复(7)

C/C++

广州市民林先生

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int k, n;
    int val;
    cin >> k >> n;
    
    vector<int> vec;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> val;
            vec.push_back(val);
        }
    }
    sort(vec.begin(),vec.end());
    cout << vec[k - 1] << endl;
    return 0;
}

发表于 2020-07-14 21:43:20 回复(0)

C/C++

嵌入式渣渣

对于这道题最简单的方式就是转为一维数组然后用快排函数，但是这样就失去了输入矩阵的意义，我觉的题目的意思就是给你个二维矩阵，利用“每行和每列元素均按升序排序”的性质输出答案。

由题意知，因为每行均有升序排列，不确定性的是不同行不同列的大小，那么搜索的时候可按列搜索，搜索方式如下：

利用num[i]记录第i行目前搜索到的数字下标，初始都为0，即第一列，每次搜索每一行第num[i]个数字中最小的数字，并排除，即num[i]++，那么第k次搜索结果即为要找的值。

第1次搜索结果：

1 5 9

10 11 13

12 13 15

第2次搜索结果

1 5 9

10 11 13

12 13 15

...

第6次搜索结果

1 5 9

10 11 13

12 13 15

...

第8次搜索结果

1 5 9

10 11 13

12 13 15

代码如下：

#include<stdio.h>
#include<stdlib.h>

int main()
{
int k, n;
int **matrix;

scanf("%d%d", &k, &n);
matrix = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++)
matrix[i] = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &matrix[i][j]);

int *num;
num = (int *)calloc(n, sizeof(int));

while (k > 1) {
int ret = n-1;
for (int i = 0; i < n; i++)
if (num[i]<n&&matrix[ret][num[ret]] > matrix[i][num[i]])
ret = i;
num[ret]++;
k--;
}

int ret = matrix[n-1][num[n-1]];
for (int i = 1; i < n; i++)
if (num[i]<n && ret > matrix[i][num[i]])
ret = matrix[i][num[i]];
printf("%d", ret);

return 0;
}

编辑于 2020-07-02 08:32:41 回复(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)

包子山

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int x;
    int k;
    cin >> k;
    vector<int> v;
    while(cin >> x)
    {
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    cout << v[k-1] << endl;
    return 0;
}

发表于 2019-11-02 10:08:05 回复(0)

向宁冋桌

#include<bits/stdc++.h>
using namespace std;
int main() {
    int k, n;
    while (cin >> k >> n) {
        int cnt = 0, t;
        multiset<int> s;
        for (int i = 0; i < n*n; i++) {
            cin >> t;
            s.insert(t);
        }
        for (auto i : s) {
            if (cnt < k-1)cnt++;
            else{
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

编辑于 2019-08-05 09:05:50 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k, n;
    while(cin>>k>>n){
        int a[n*n];
        for(int i=0;i<n*n;i++)
            cin>>a[i];
        sort(a,a+n*n);
        cout<<a[k-1]<<endl;
    }
    return 0;
}

发表于 2019-07-12 21:47:41 回复(0)

C/C++

ElonB

/*
时间复杂度没控制，变成了排序题
*/
#include<bits/stdc++.h>
using namespace std;
#define N 10000

int main()
{
//    freopen("input.txt", "r", stdin);
    int k, n;
    cin >> k >> n;
    vector<int> a(n * n);
    for(int i = 0; i < n * n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    cout << a[k - 1] << endl;
    return 0;
}

编辑于 2019-07-12 11:51:19 回复(1)

瓜子儿。

这个题应该不能直接用sort吧。。不然还有啥意义

思路：

1.分析可知位于数组arr[i][j]位置的数只能放在列表 [i*j,n*(i-1)+j]这个小区间(为了分析方便这里i,j,n都从1开始)，所以我们可以构建一个插入有序的列表

2.对于每一个新加入列表的数，如果i*j位置可以放则放，如果不能放则继续往后看直到找到能放的位置——即不需要对结束条件进行判定

细节：频繁插入用linkedlist，初始列表必须add()一个数据避免循环开始的时候报错，而且只需要add()一个数据

优化：上述1中说每次新增元素arr[i][j]从[i*j]开始其实有点多余了，就像字符串匹配每次倒回去很远一样，加了一个辅助空间location[i][j]代表arr[i][j]元素初次插入list的位置<没有动态更新，因为我不会>

//获取arr[][]略
int[][] location=new int[n+1][n+1];
List<Integer> list=new LinkedList<>();
list.add(0);

for(int i=0;i<n;i++) {
   for(int j=0;j<n;j++) {
       int start=location[i+1][j]>location[i][j+1]?location[i+1][j]:location[i][j+1];
       while(list.get(start)!=0&&list.get(start)<arr[i][j])
           start++;
       location[i+1][j+1]=start;
       list.add(start, arr[i][j]);
   }
}System.out.println(list.get(target-1));

编辑于 2019-08-05 23:00:46 回复(3)

pein531

这题本应该用二分或者快速选择算法来做，但是发现暴力法也可以AC，简直了

k, n = map(int, input().strip().split())
matrix = []
for _ in range(n):
    matrix.extend(list(map(int, input().strip().split())))
print(sorted(matrix)[k - 1])

发表于 2021-04-16 19:32:02 回复(0)

C/C++

谢莲花

知识点：数组+排序

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int k,n;
	while(cin>>k>>n)
	{
		int a[n*n];
		for(int i=0;i<n*n;i++)
			cin>>a[i];
		sort(a,a+n*n);
		cout<<a[k-1]<<endl;
	}
	return 0;
}

发表于 2020-08-20 10:58:52 回复(0)

C/C++

有梦想的小丑

//采用最大堆维持最小的k个数，堆顶就是答案

#include<iostream>
(720)#include<queue>
using namespace std;
int main()
{
    int k,n;
    while(cin>>k>>n)
    {
        priority_queue<int> p;
        int x;
        while(cin>>x)
        {
            p.push(x);
            if(p.size()>k)
                p.pop();
        }
        cout<<p.top()<<endl;
    }
    return 0;
}

发表于 2020-03-04 14:40:16 回复(0)

JavaScript

萌萌萌哒

JavaScript(Node) 😎题目:唯品会💄-有序矩阵中第K小的元素(sort就完事了)

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
let n
rl.on('line',line=>{
    if(!line) return
    inArr.push(line)
    if(inArr.length === 1){
        k = +inArr[0].split(' ')[0]
        n = +inArr[0].split(' ')[1]
    }
    if(inArr.length === n+1){
        let res = []
        let ans
        for (let i = 0; i < n; i++) {
             res[i] = inArr[i+1].split(' ').map(e => +e)
        }
        res = [].concat(...res).sort((a,b) => a-b)
        ans = res[k-1]
        console.log(ans)
    }
})

发表于 2020-03-01 17:36:49 回复(0)

Python

卷积神经网络哦

Python三行咯暴力

k, n = [int(x) for x in input().split(' ')]
a = [[int(x) for x in input().split(' ')] for j in range(n)]
print(sorted([y for x in a for y in x])[k-1])

发表于 2019-12-05 09:04:41 回复(0)

dragonlogin

#include<bits/stdc++.h>
using namespace std;
int main() {
	int k, n;
	cin >> k >> n;
	vector<int> f(n*n);
	for (int i=0; i<n; ++i) {
		for (int j=0; j<n; ++j) {
			cin >> f[i*n+j];
		}
	}

	sort(f.begin(), f.end());
	cout << f[k-1] <<endl;
	return 0;
}

发表于 2019-10-19 15:16:36 回复(0)

EnvyEvil

k, n = list(map(int, input().split()))
n_matrix = [list(map(int, input().split())) for i in range(n)]
# 新建一个一维list用来储存n_matrix
n_list = []
for i in range(n):
    n_list += n_matrix[i]
# 排序后直接输出对应数字即可
n_list.sort()
print(n_list[k - 1])

发表于 2019-09-10 15:41:19 回复(0)

无心2019

#include<bits/stdc++.h> 
using namespace std; 
int main()
{
    int k,n;
    cin>>k>>n;
    int num[n][n];
    vector<int>res;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            cin>>num[i][j];
            res.push_back(num[i][j]);
        }
    sort(res.begin(),res.end());
    cout<<res[k-1]<<endl;
    return 0;
}

发表于 2019-07-03 11:42:56 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "sort"
)

func main() {
    var k,n int
    fmt.Scan(&k,&n)
    arr:=[]int{}
    var x int
    for{
        _,ok:=fmt.Scan(&x)
        if ok!=nil{
            break
        }
        arr=append(arr,x)
    }
    sort.Ints(arr)
    fmt.Print(arr[k-1])
}

发表于 2023-03-21 22:06:47 回复(0)

勇敢牛牛，不怕困难！

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
  int k, n, x;
  cin >> k >> n;
  vector<int> nums;
  for (int i = 0; i < n * n; ++i) {
    cin >> x;
    nums.emplace_back(x);
  }
  
  sort(begin(nums), end(nums));
  cout << nums[k - 1] << endl;
  return 0;
}

发表于 2021-07-13 18:56:33 回复(0)

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)