给定一个
的整形矩阵matrix和一个整数K, matrix的每一行和每一列都是排好序的。
实现一个函数，判断K是否在matrix中
[要求]
时间复杂度为)
，额外空间复杂度为)
。
[编程题]在行列都排好序的矩阵中找指定的数
这题一般的思路是从右上角或者左下角开始查找，如果k大于右上角的值，就排除第一行，反之排除最后一列，如此反复进行，这样算法的时间复杂度就是O(M + N)。
这里给出一种不同的思路，算法时间复杂度或许能下降到O(lg(N) * lg(M))，（为什么是“或许”？因为我也不会算这个复杂度啊🤣,有没有大神帮忙算一下告诉我）。
如图所示，每次在中间选一行，用二分查找在这一行中找插入位置，那么在插入位置左上角的区域都比目标值大，右下角区域都比目标值小，这样可以排除矩阵中一半的内容。即使没有找到插入位置，也就是插入位置在最前面或者最后的情况，也可以排除一半。然后对剩余的两个矩阵递归查找。
这样每次二分查找的时间是lg（M），递归次数是lg（N）？时间复杂度就是O(lg(N) * lg(M))？空间复杂度和递归深度相关，为lg（N）。
#include<vector>
#include<iostream>
using namespace std;
// 在矩阵中查找目标值，存在就返回true
bool Find(int target, vector<vector<int>> &matrix);
// 在矩阵matrix中，左上角坐标为(r1, c1),右下角坐标为(r2, c2)的子矩阵中查找target
bool sM(vector<vector<int>> &matrix,int target,int r1,int c1,int r2,int c2);
// 在数组nums的下标f到l之间，用二分查找target，返回target的插入位置
int difind(vector<int> &nums,int target,int f,int l);
int main(){
int n;
cin >> n;
int m;
cin >> m;
int k;
cin >> k;
vector<vector<int>> matrix(n, vector<int>(m, 0));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> matrix[i][j];
}
}
if(Find(k, matrix)){
cout << "Yes";
}
else{
cout << "No";
}
}
bool Find(int target, vector<vector<int>> &matrix) {
if(matrix.empty()||matrix[0].empty()) return false;
return sM(matrix,target,0,0,matrix.size()-1,matrix[0].size()-1);
}
bool sM(vector<vector<int>> &matrix,int target,int r1,int c1,int r2,int c2)
{
if(r1>r2||c1>c2) return false;
int mid=r1+((r2-r1)>>1);
int pos=difind(matrix[mid],target,c1,c2);
if(pos<c1)
{
return sM(matrix,target,r1,c1,mid-1,c2);
}
else if(pos==c2)
{
if(matrix[mid][pos]==target) return true;
return sM(matrix,target,mid+1,c1,r2,c2);
}
else
{
if(matrix[mid][pos]==target) return true;
return sM(matrix,target,r1,pos+1,mid-1,c2)||sM(matrix,target,mid+1,c1,r2,pos);
}
}
int difind(vector<int> &nums,int target,int f,int l)
{
if(f==l)
{
return target>=nums[f]?f:f-1;
}
if(l-f==1)
{
if(nums[f]==target) return f;
else if(nums[f]>target) return f-1;
else return target>=nums[l]?l:l-1;
}
int mid=f+((l-f)>>1);
if(nums[mid]==target)return mid;
else if(nums[mid]>target) return difind(nums,target,f,mid-1);
else return difind(nums,target,mid+1,l);
}
编辑于 2019-08-12 09:46:19
回复(4)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>>num(n,vector<int>(m));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>num[i][j];
int i=0,j=m-1,res=0;
while(i<n&&j>=0)
{
if(num[i][j]>k)
{
j--;
}
else if(num[i][j]<k)
i++;
else
{
res=1;
break;
}
}
if(res==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
return 0;
}
发表于 2019-08-22 22:31:58
回复(1)
Java解法
思路
一开始将指针定位在矩阵matrix的左上角，即i = 0, j = matrix[0].length - 1，当前元素为matrix[i][j]
matrix[i][j] < k时，i++，即指针向下移动；
matrix[i][j] > k时，j--，即指针向左移动；
matrix[i][j] == k时，说明找到了元素。
import java.util.Scanner;
public class Main {
public static boolean ifKInMatrix(int[][] matrix, int k) {
int rows = matrix.length;
int cols = matrix[0].length;
int i = 0;
int j = cols - 1;
while (i < rows && j >= 0) {
if (matrix[i][j] < k) {
i++;
} else if (matrix[i][j] > k) {
j--;
} else {
return true;
}
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int[][] matrix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = sc.nextInt();
}
}
boolean res = ifKInMatrix(matrix, k);
if (res) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
发表于 2019-10-10 16:18:40
回复(1)
利用行和列都排好序的信息，从右上角开始搜索，遇到大于target的元素，就往左边的列继续找，遇到小于target的元素就往下面的行继续找。最差情况从右上角移动到左下角才找到，算法的时间复杂度为O(N+M)，仅使用有限几个变量(行指针和列指针)，空间复杂度为O(1)
import scala.io.StdIn
object Main{
def main(args: Array[String]): Unit = {
val in = StdIn
var params = in.readLine().split(" ")
val n = params(0).toInt
val m = params(1).toInt
val k = params(2).toInt
val arr = Array.ofDim[Int](n, m)
for(i <- arr.indices){
params = in.readLine().split(" ")
for(j <- arr(0).indices)
arr(i)(j) = params(j).toInt
}
println(search(arr, n, m, k))
}
def search(arr: Array[Array[Int]], n: Int, m: Int, k: Int): String = {
var row = 0
var col = m - 1
while(row < n && col >= 0){
if(arr(row)(col) > k){
col -= 1
}else if(arr(row)(col) < k){
row += 1
}else{
return "Yes"
}
}
"No"
}
}
发表于 2021-11-19 22:37:46
回复(0)
<pre class="prettyprint lang-py"><span />import numpy as np #空格输入三个整数 N,M,K = map(int,input().split(' ')) #定义二维数组并输入 a = [] for i in range(N): a.append(list(map(int, input().rstrip().split()))) #判读是否在数组中 isIn = 0 for i in range(N): for j in range(M): if a[i][j] == K: isIn = 1 break elif a[i][j] > K: M = j if isIn == 0: print("No") else: print("Yes") </pre> <div> 第一种方案：减少遍历 </div> <div> <pre class="prettyprint lang-py">#空格输入三个整数 N,M,K = map(int,input().split(' ')) #定义二维数组并输入 a = [] for i in range(N): a.append(list(map(int, input().rstrip().split()))) #判读是否在数组中 isIn = 0 for i in range(N): ls = a[i] if K in ls: isIn = 1 break if isIn == 0: print("No") else: print("Yes")</pre> <span>第二种方案(全遍历)：使用 in 判断</span><br /> <br /> </div>
编辑于 2019-08-12 11:56:33
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Integer N = sc.nextInt();
Integer M = sc.nextInt();
Integer K = sc.nextInt();
Integer[][] arr = new Integer[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j< M; j++) {
arr[i][j] = sc.nextInt();
}
}
// 从右上角开始，k比该值大就往下走，比该值小就往左走，直到超出界限
Integer row = M - 1;
Integer cow = 1;
boolean flag = false;
while(row >= 0 && cow <= N-1){
if (arr[cow][row] > K) {
row--;
} else if (arr[cow][row] < K) {
cow++;
} else {
flag = true;
break;
}
}
if (flag) {
System.out.print("Yes");
} else {
System.out.print("No");
}
}
}
编辑于 2019-08-02 09:42:35
回复(1)
直接遍历，调用Arrays.binarySearch()的系统方法
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int a[][] = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
for (int i = 0; i < n; i++) {
int index = Arrays.binarySearch(a[i], k);
if (index >= 0) {
System.out.println("Yes");
return;
} else {
if (i == n - 1)
System.out.println("No");
}
}
}
}
发表于 2020-09-08 09:23:34
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, k;
cin>>n>>m>>k;
int a[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
int x=0, y=m-1, r=0;
while(x<n && y>=0){
if(a[x][y]==k){
r = 1;
break;
}
if(k>a[x][y])
x++;
else
y--;
}
cout<<(r==1?"Yes":"No")<<endl;
return 0;
}
发表于 2020-01-26 02:51:52
回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main(){
int N=0,M=0,K=0;
cin>>N>>M>>K;
vector<vector<int>> val(N,vector<int>(M));
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin>>val[i][j];
}
}
//根据矩阵的特性从右上角这个数开始查找
int r=0,l=M-1;
while(r<N && l>=0){
if(K==val[r][l]) {
cout<<"Yes"<<endl;
return 0;
}
//如果K大于这个数，这一行的数都不用遍历了
if(K>val[r][l]){
r++;
}else{ //如果K小于这个数，这一列的数都不用遍历了
l--;
}
}
cout<<"No"<<endl;
}
发表于 2019-08-09 09:47:04
回复(0)
package main
import (
"fmt"
"bufio"
"strings"
"strconv"
"os"
)
func main() {
var (
k int
index int
max_num int
)
in := bufio.NewScanner(os.Stdin)
for in.Scan() {
strs := strings.Split(in.Text(), " ")
if index == 0 {
k, _ = strconv.Atoi(strs[len(strs)-1])
}else {
max_num, _ = strconv.Atoi(strs[len(strs)-1])
}
index = index + 1
}
if max_num > k {
fmt.Println("Yes")
}else {
fmt.Println("No")
}
}
发表于 2022-11-16 15:06:47
回复(0)
#include <iostream>
using namespace std;
int ma[1001][1001];
bool contains(int x, int y, int val) {
if(x < 0 || y < 0) {return false;}
if (ma[x][y] == val) {
return true;
} else if(ma[x][y] < val) {
return false;
} else {
return contains(x-1, y, val) || contains(x, y-1, val);
}
}
int main() {
int a, b, K;
cin >> a >> b >> K;
for(int i = 0; i < a; i++) {
for(int j = 0; j < b; j++) {
cin>>ma[i][j];
}
}
cout<< (contains(a-1, b-1, K) ? "Yes" : "No");
}
using namespace std;
int ma[1001][1001];
bool contains(int x, int y, int val) {
if(x < 0 || y < 0) {return false;}
if (ma[x][y] == val) {
return true;
} else if(ma[x][y] < val) {
return false;
} else {
return contains(x-1, y, val) || contains(x, y-1, val);
}
}
int main() {
int a, b, K;
cin >> a >> b >> K;
for(int i = 0; i < a; i++) {
for(int j = 0; j < b; j++) {
cin>>ma[i][j];
}
}
cout<< (contains(a-1, b-1, K) ? "Yes" : "No");
}
发表于 2022-06-14 23:42:24
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[]args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[][]mat = new int[N][M];
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
mat[i][j] = sc.nextInt();
}
}
boolean hasFound = false;
int i = N - 1, j = 0;
while(i >= 0 && j < M){
if (mat[i][j] > K) i--;
else if (mat[i][j] < K) j++;
else {
hasFound = true;
break;
}
}
if (hasFound) System.out.println("Yes");
else System.out.println("No");
}
}
发表于 2022-05-23 16:43:45
回复(0)
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int main() {
int m = 0, n = 0, k = 0;
scanf("%d %d %d", &m, &n, &k);
vector<vector<int>> matrix(m, vector<int>(n));
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
scanf("%d", &matrix[i][j]);
}
}
int i = 0;
int j = matrix[0].size() - 1;
while(i < matrix.size() && j >= 0){
if(matrix[i][j] > k){
j--;
}
else if(matrix[i][j] < k){
i++;
}
else {
printf("Yes\n");
return 0;
}
}
printf("No\n");
return 0;
}
发表于 2022-05-17 19:14:10
回复(0)
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer=new BufferedWriter(new OutputStreamWriter(System.out));
String s1=reader.readLine();
String[] split1=s1.split(" ");
int n=Integer.parseInt(split1[0]);
int m=Integer.parseInt(split1[1]);
int k=Integer.parseInt(split1[2]);
int[][] nums=new int[n][m];
for(int i=0;i<n;i++){
String s2=reader.readLine();
String[] split2=s2.split(" ");
for(int j=0;j<m;j++){
nums[i][j]=Integer.parseInt(split2[j]);
}
}
int i=0,j=m-1;
while(i<n&&j>=0){
if(nums[i][j]==k){
writer.write("Yes");
writer.flush();
return;
}else if(nums[i][j]>k){
j--;
}else{
i++;
}
}
writer.write("No");
writer.flush();
writer.close();
reader.close();
}
}
发表于 2022-05-08 15:56:39
回复(0)
该牛油正在参与牛客写题解薅羊毛的活动，牛币，周边，京东卡超多奖品放送，活动进入倒计时！，活动进入倒计时！快来捡漏啦https://www.nowcoder.com/discuss/888949?source_id=profile_create_nctrack&channel=-1
发表于 2022-04-26 16:02:57
回复(0)
#include<iostream>
using namespace std;
int main()
{
long long a,b,c;
cin >> a >> b >> c;
int p[1000][1000] = { 0 };
for (int i = 0; i < a; i++)
{
for (int u = 0; u < b; u++)
{
cin >> p[i][u];
}
}
int g = 0;
for (int i = 0; i < a; i++)
{
for (int u = 0; u < b; u++)
{
if (c == p[i][u])
{
g++;
}
}
}
if (g != 0)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
using namespace std;
int main()
{
long long a,b,c;
cin >> a >> b >> c;
int p[1000][1000] = { 0 };
for (int i = 0; i < a; i++)
{
for (int u = 0; u < b; u++)
{
cin >> p[i][u];
}
}
int g = 0;
for (int i = 0; i < a; i++)
{
for (int u = 0; u < b; u++)
{
if (c == p[i][u])
{
g++;
}
}
}
if (g != 0)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
发表于 2022-03-31 16:10:29
回复(0)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int[][] nm = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
nm[i][j] = sc.nextInt();
}
}
for(int i = 0; i < n; i++){
if(k >= nm[i][0] && k <= nm[i][m-1]){
for(int j = 0 ; j < m; j++){
if(nm[i][j] == k){
System.out.println("Yes");
return;
}
}
}
}
System.out.println("No");
}
}
发表于 2022-03-18 21:31:34
回复(0)
s = input().split(' ')
a = []
for i in range(int(s[0])):
a += input().split(' ')
if s[2] in a:
print('Yes')
else:
print('No')
发表于 2022-03-18 13:11:39
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-14 22:14:51 -
2022-09-14 00:18:17
-
2022-09-13 10:47:10 -
2022-09-13 00:14:40
-
2022-09-11 18:51:57
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
