牛客NC86 矩阵元素查找【中等分治，减治 C++/Java/Go/PHP】

本文主要是介绍牛客NC86 矩阵元素查找【中等分治，减治 C++/Java/Go/PHP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/3afe6fabdb2c46ed98f06cfd9a20f2ce

思路

选择左下角为起点，以下展示了「减治」的过程。
搜索的规律是：如果当前数比目标元素小，当前列就不可能存在目标值，「指针」就向右移一格（纵坐标加 1）；
如果当前数比目标元素大，当前行就不可能存在目标值，「指针」就向上移一格（横坐标减 1）。
在编码的过程中要注意数组下标越界的问题。

参考答案C++

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param mat int整型vector<vector<>> * @param n int整型 * @param m int整型 * @param x int整型 * @return int整型vector*/vector<int> findElement(vector<vector<int> >& mat, int n, int m, int x) {/*选择左下角为起点，以下展示了「减治」的过程。搜索的规律是：如果当前数比目标元素小，当前列就不可能存在目标值，「指针」就向右移一格（纵坐标加 1）；如果当前数比目标元素大，当前行就不可能存在目标值，「指针」就向上移一格（横坐标减 1）。在编码的过程中要注意数组下标越界的问题。*/// 起点：左下角int currow = n-1;int curcol = 0;// 不越界的条件是：行大于等于 0，列小于等于 cols - 1vector<int> ans = {-1,-1};while (currow >=0 && curcol<m){if(mat[currow][curcol] >x ){currow-=1;}else if(mat[currow][curcol] <x){curcol+=1;}else{ans[0] =currow;ans[1] =curcol;break;}}return ans;}
};

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param mat int整型二维数组* @param n int整型* @param m int整型* @param x int整型* @return int整型一维数组*/public int[] findElement (int[][] mat, int n, int m, int x) {/*选择左下角为起点，以下展示了「减治」的过程。搜索的规律是：如果当前数比目标元素小，当前列就不可能存在目标值，「指针」就向右移一格（纵坐标加 1）；如果当前数比目标元素大，当前行就不可能存在目标值，「指针」就向上移一格（横坐标减 1）。在编码的过程中要注意数组下标越界的问题。*/// 起点：左下角int currow = n - 1;int curcol = 0;// 不越界的条件是：行大于等于 0，列小于等于 cols - 1while (currow >= 0 && curcol < m) {if (mat[currow][curcol] > x) {currow -= 1;} else if (mat[currow][curcol] < x) {curcol += 1;} else {return new int[] {currow, curcol};}}return new int[] {-1, -1};}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param mat int整型二维数组* @param n int整型* @param m int整型* @param x int整型* @return int整型一维数组*/
func findElement(mat [][]int, n int, m int, x int) []int {/*选择左下角为起点，以下展示了「减治」的过程。搜索的规律是：如果当前数比目标元素小，当前列就不可能存在目标值，「指针」就向右移一格（纵坐标加 1）；如果当前数比目标元素大，当前行就不可能存在目标值，「指针」就向上移一格（横坐标减 1）。在编码的过程中要注意数组下标越界的问题。*/// 起点：左下角currow := n - 1curcol := 0ans := []int{-1, -1}// 不越界的条件是：行大于等于 0，列小于等于 cols - 1for currow >= 0 && curcol < m {if mat[currow][curcol] > x {currow -= 1} else if mat[currow][curcol] < x {curcol += 1} else {ans[0] = currowans[1] = curcolbreak}}return ans
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param mat int整型二维数组 * @param n int整型 * @param m int整型 * @param x int整型 * @return int整型一维数组*/
function findElement( $mat ,  $n ,  $m ,  $x )
{/*选择左下角为起点，以下展示了「减治」的过程。搜索的规律是：如果当前数比目标元素小，当前列就不可能存在目标值，「指针」就向右移一格（纵坐标加 1）；如果当前数比目标元素大，当前行就不可能存在目标值，「指针」就向上移一格（横坐标减 1）。在编码的过程中要注意数组下标越界的问题。*/// 起点：左下角$currow = $n-1;$curcol = 0;$ans = [-1,-1];while ($currow >=0 && $curcol < $m){if($mat[$currow][$curcol] > $x) {$currow-=1;}else if($mat[$currow][$curcol] < $x){$curcol+=1;}else{$ans[0] =$currow;$ans[1] =$curcol;break;}}return $ans;
}