给定一个
的整形矩阵matrix和一个整数K, matrix的每一行和每一列都是排好序的。
实现一个函数，判断K是否在matrix中
[要求]
时间复杂度为)
，额外空间复杂度为)
。
[编程题]在行列都排好序的矩阵中找指定的数
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)
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)
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)
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[][] matrix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = sc.nextInt();
}
}
search(matrix, k);
}
private static void search(int[][] arr, int targt){
if(arr == null || arr.length < 1 || arr[0].length < 1){
System.out.println("No");
return;
}
int i = 0;
int j = arr[0].length - 1;
while(i <= arr[0].length - 1 && j >= 0){
if(arr[i][j] == targt){
System.out.println("Yes");
return;
}
if(arr[i][j] > targt){
j--;
}else{
i++;
}
}
System.out.println("No");
}
}
发表于 2021-09-22 20:43:36
回复(0)
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)
根据图解大佬的解题思路终于做出来了（笑哭）
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt(),m=scanner.nextInt(),k=scanner.nextInt();
int[][] matrix = new int[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
matrix[i][j]=scanner.nextInt();
int i=0,flag=0;
while(i<n&&m>0){
if(matrix[i][m-1]==k){
flag=1;break;
}else if(matrix[i][m-1]<k)
i++;
else
m--;
}
if(flag==1)
System.out.println("Yes");
else
System.out.println("No");
}
}
发表于 2019-09-07 11:17:40
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int M = s.nextInt();
int K = s.nextInt();
// System.out.print(N + " " + M + " " + K);
int[][] array = new int[N][M];
for (int i = 0;i < N;i++) {
for (int j = 0;j < M;j++) {
array[i][j] = s.nextInt();
}
}
//根据矩阵的特性从右上角这个数开始查找,逼近
int r = 0;
int l = M - 1;
int find_flag = 0;
while (r < N && l > -1) {
if (K == array[r][l]) {
find_flag = 1;
System.out.print("Yes");
}
if (K > array[r][l]) { //若大于右上角这个数,则这一行不用找了,直接换行
r++;
}else if (K < array[r][l]){ //若小于右上角这个数,则这一列不用找了,直接换列
l--;
}else if (K == array[r][l]) {
System.out.print("Yes");
return;
}
}
System.out.print("No");
}
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int M = s.nextInt();
int K = s.nextInt();
// System.out.print(N + " " + M + " " + K);
int[][] array = new int[N][M];
for (int i = 0;i < N;i++) {
for (int j = 0;j < M;j++) {
array[i][j] = s.nextInt();
}
}
//根据矩阵的特性从右上角这个数开始查找,逼近
int r = 0;
int l = M - 1;
int find_flag = 0;
while (r < N && l > -1) {
if (K == array[r][l]) {
find_flag = 1;
System.out.print("Yes");
}
if (K > array[r][l]) { //若大于右上角这个数,则这一行不用找了,直接换行
r++;
}else if (K < array[r][l]){ //若小于右上角这个数,则这一列不用找了,直接换列
l--;
}else if (K == array[r][l]) {
System.out.print("Yes");
return;
}
}
System.out.print("No");
}
}
可是最后只通过了40%，不知道什么原因，希望大佬们指点一下
发表于 2019-08-15 16:03:04
回复(1)
问题信息
通过挑战的用户
查看代码-
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号
