• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

directory

  1. Title Description:Find elements in a matrix
  2. Violence lawTo find the
  3. Law to find
  4. Recursive search
  5. reference

Title description:Find elements in a matrix

In a two-dimensional array (each one-dimensional array is the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

The existing matrix matrix is as follows:


var arr1  = [
    [1.2.3],
    [4.5.6],
    [7.8.9]]. A given target =5To return totrueA given target =20To return tofalse

Copy the code

twoViolence lawTo find the

Iterate over all the elements in the array to see if they exist.

Time is O(N^2), space is O(1).

var arr = [
  [1.4.7.11.13],
  [2.5.8.12.19],
  [3.6.9.16.22],
  [10.13.14.17.24],
  [18.21.22.25.37]].function findTargetInList(list, target){
    if(list.length===0) return false
    let rowLength = list.length;
    let colLength = list[0].length;
    for(let i=0; i< rowLength; i++){
        for(let j=0; j<colLength; j++){
            if(list[i][j] === target){ 
                return true}}}return false;
};
findTargetInList(arr,2); // true
findTargetInList([],2); // false
findTargetInList([[],[]],1); // false
Copy the code

Three rule search

Time is O(M+N), space is O(1). Where M and N represent the number of rows and columns respectively.

var findNumIn2DArr = function(matrix, target) {
    if(matrix.length == 0)
        return false;

    let x = 0;
    let y = matrix.length - 1;

    while(x < matrix[0].length && y >= 0) {if(matrix[y][x] > target) {
            y--;
        } else if(matrix[y][x] < target) {
            x++;
        } else {
            return true; }}return false;
};
var arr1  = [
    [1.2.3],
    [4.5.6],
    [7.8.9]]. findNumIn2DArr(arr1,10); // false

Copy the code

Quad recursive search

Consider a two-dimensional array as a plane coordinate system, starting from the lower left corner (0,arr. Length-1) :

  • The target value is greater than the coordinate value –x +1
  • The target value is less than the coordinate value –y coordinate -1
var arr = [
  [1.4.7.11.13],
  [2.5.8.12.19],
  [3.6.9.16.22],
  [10.13.14.17.24],
  [18.21.22.25.37]].function find(target, array) {

  let i = array.length - 1; / / y

  let j = 0; / / x coordinate

  return compare(target, array, i, j);
}

 

function compare(target, array, i, j) {

  if (array[i] === undefined || array[i][j] === undefined) {

    return false;

  }

  const temp = array[i][j];

  if (target === temp) {

    return true;

  }

  else if (target > temp) {

    return compare(target, array, i, j+1);

  }

  else if (target < temp) {

    return compare(target, array, i-1, j);

  }

}
find(21, arr); // true
Copy the code

reference

  • Lookup in a two-dimensional array
  • Time complexity