Элемент поиска в матрице

Опубликовано: 26 Февраля, 2023

Учитывая матрицу N×N mat[][] и целое число K , задача состоит в том, чтобы найти K в mat[][] и, если он найден, вернуть его индексы.

Примеры:

Input: mat[][] = {{1, 2, 3}, {7, 6, 8}, {9, 2, 5}}, K = 6
Output: {1, 1}
Explanation: mat[1][1] = 6
Input: mat[][] = {{3, 4, 5, 0}, {2, 9, 8, 7}}, K = 10
Output: Not Found

Подход:

Traverse the matrix using nested loops and if the target is found then, return its indices

Следуйте инструкциям, чтобы решить эту проблему:

Возьмите матрицу (двумерный массив) и цель в качестве входных данных.
Примените два вложенных цикла for с переменными i и j соответственно.
- Если mat[i][j] = K вернуть пару индексов {i, j}
Если цель не найдена, выведите «Not Found».

Ниже приведена реализация этого подхода

C++

// C++ code to search in a Matrix
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to search a number in a matrix
pair<int, int> FindPosition(vector<vector<int> > M,
                            int K)
{
    for (int i = 0; i < M.size(); i++) {
        for (int j = 0; j < M[i].size(); j++) {
            if (M[i][j] == K)
                return { i, j };
        }
    }
    return { -1, -1 };
}
 
// Driver code
int main()
{
    // Taking the 2D Array
    vector<vector<int> > M{ { 1, 2, 3 },
                            { 7, 6, 8 },
                            { 9, 2, 5 } };
    int K = 6;
 
    // Function call
    pair<int, int> p = FindPosition(M, K);
    if (p.first == -1)
        cout << "Not Found" << endl;
    else
        cout << p.first << " " << p.second;
    return 0;
}

Java

// Java code to search in a Matrix
class Pair {
  int first;
  int second;
 
  Pair(int _first, int _second) {
    first = _first;
    second = _second;
  }
}
 
class GFG {
 
  // Function to search a number in a matrix
  static Pair FindPosition(int[][] M, int K) {
    for (int i = 0; i < M.length; i++) {
      for (int j = 0; j < M[i].length; j++) {
        if (M[i][j] == K)
          return new Pair(i, j);
      }
    }
    return new Pair(-1, -1);
  }
 
  // Driver code
  public static void main(String args[])
  {
     
    // Taking the 2D Array
    int[][] M = { { 1, 2, 3 },
                 { 7, 6, 8 },
                 { 9, 2, 5 } };
    int K = 6;
 
    // Function call
    Pair p = FindPosition(M, K);
    if (p.first == -1)
      System.out.println("Not Found");
    else
      System.out.println(p.first + " " + p.second);
  }
}
 
// This code is contributed by _saurabh_jaiswal.

Python3

# Function to search a number in a matrix
def FindPosition(M,K):
  ans = []
  for i in range(0,len(M)):
    for j in range(0,len(M[0])):
      if (M[i][j] is K):
        ans.append(i)
        ans.append(j)
        return ans
         
         
  ans.append(-1)
  ans.append(-1)
  return ans
   
M = [[ 1, 2, 3 ],[ 7, 6, 8 ],[ 9, 2, 5]]
K = 6
 
# Function call
p = FindPosition(M,K)
if (p[0] is -1):
  print("Not Found")
else:
  print(p[0],p[1]) 
 
# This code is contributed by akashish__

C#

// Include namespace system
using System;
public class GFG
{
    // Function to search a number in a matrix
    public static int[] FindPosition(int[,] M, int K)
    {
        for (int i = 0; i < M.GetLength(0); i++)
        {
            for (int j = 0; j < M.GetLength(1); j++)
            {
                if (M[i,j] == K)
                {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
   
    // Driver code
    public static void Main(String[] args)
    {
        // Taking the 2D Array
        int[,] M = {{1, 2, 3}, {7, 6, 8}, {9, 2, 5}};
        var K = 6;
       
        // Function call
        int[] p = GFG.FindPosition(M, K);
        if (p[0] == -1)
        {
            Console.WriteLine("Not Found");
        }
        else
        {
            Console.WriteLine(p[0].ToString() + " " + p[1].ToString());
        }
    }
}
 
// This code is contributed by aadityapburujwale

Javascript

<script>
// Javascript code to search in a Matrix
 
// Function to search a number in a matrix
function FindPosition( M, K)
{
    for (let  i = 0; i < M.length; i++) {
        for (let j = 0; j < M[i].length; j++) {
            if (M[i][j] == K){
                let ans = new Array( i, j );
                return ans;
                }
        }
    }
    let ans=new Array( -1, -1  );
    return ans;
 }
 
// Driver code
 
    // Taking the 2D Array
    let  M=[ [ 1, 2, 3 ],
              [ 7, 6, 8 ],
              [ 9, 2, 5 ] ];
    let K = 6;
 
    // Function call
    let p=new Array();
    p = FindPosition(M, K);
    if (p[0] == -1){
        document.write("Not Found" );
        document.write("<br>");
        }
    else
       document.write(p[0]+" " + p[1]);
        
       // This code is contributed by satwik4409.
   </script>

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)

Школьное программирование

Элемент поиска в матрице

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ