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

题目

题目链接：
https://www.nowcoder.com/practice/3afe6fabdb2c46ed98f06cfd9a20f2ce

思路

选择左下角为起点，以下展示了「减治」的过程。
搜索的规律是：

如果当前数比目标元素小，当前列就不可能存在目标值，「指针」就向右移一格（纵坐标加 1）；
如果当前数比目标元素大，当前行就不可能存在目标值，「指针」就向上移一格（横坐标减 1）。
在编码的过程中要注意数组下标越界的问题。
1
2
3
4
5
6

参考答案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 - 1
        vector<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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

参考答案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 - 1
        while (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};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

参考答案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 - 1
	curcol := 0

	ans := []int{-1, -1}
	// 不越界的条件是：行大于等于 0，列小于等于 cols - 1
	for 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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

参考答案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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41