Encuentre la fila con el máximo de elementos únicos en Matrix dada

Dada una array arr[][] de tamaño N*M , la tarea es encontrar el índice de la fila que tiene el máximo de elementos únicos. Si hay varias filas posibles, devuelva la fila indexada mínima.

Ejemplos: 

Entrada: arr[][] = { {1, 2, 3, 4, 5}, {1, 2, 2, 4, 7}, {1, 3, 1, 3, 1} }       
Salida: 0
Explicación: Las filas 0, 1 y 2 tienen 5, 4 y 2 elementos únicos respectivamente.
 

Entrada: arr[][] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 1, 2, 3} }
Salida: 0

Enfoque : La tarea se puede resolver utilizando una estructura de datos establecida . Itere sobre las filas y almacene el elemento correspondiente dentro de un conjunto para realizar un seguimiento de los elementos únicos , devuelva la fila indexada mínima con el máximo de elementos únicos.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum indexed row
// with maximum unique elements
int get(int n, int m, vector<vector<int> >& v)
{
    // Stores the unique elements
    set<int> s;
 
    // Stores the minimum indexed row
    int max_ans = INT_MAX;
    int cnt = -1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            s.insert(v[i][j]);
        }
        int size = (int)s.size();
        if (cnt < size) {
            size = cnt;
            max_ans = min(max_ans, i);
        }
        s.clear();
    }
    return max_ans;
}
 
// Driver Code
int main()
{
 
    vector<vector<int> > arr
        = { { 1, 2, 3, 4, 5 },
            { 1, 2, 2, 4, 7 },
            { 1, 3, 1, 3, 1 } };
    int n = arr.size();
    int m = arr[0].size();
    cout << get(n, m, arr);
}

// JAVA program for the above approach
import java.util.*;
class GFG
{
 
  // Function to find the minimum indexed row
  // with maximum unique elements
  public static int get(int n, int m,
                        ArrayList<ArrayList<Integer> > v)
  {
    // Stores the unique elements
    HashSet<Integer> s = new HashSet<Integer>();
 
    // Stores the minimum indexed row
    int max_ans = Integer.MAX_VALUE;
    int cnt = -1;
 
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        s.add(v.get(i).get(j));
      }
      int size = (int)s.size();
      if (cnt < size) {
        size = cnt;
        max_ans = Math.min(max_ans, i);
      }
      s.clear();
    }
    return max_ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    ArrayList<ArrayList<Integer> > arr
      = new ArrayList<ArrayList<Integer> >();
    ArrayList<Integer> temp1
      = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    ArrayList<Integer> temp2
      = new ArrayList<>(Arrays.asList(1, 2, 2, 4, 7));
    ArrayList<Integer> temp3
      = new ArrayList<>(Arrays.asList(1, 3, 1, 3, 1));
    arr.add(temp1);
    arr.add(temp2);
    arr.add(temp3);
    int n = arr.size();
    int m = arr.get(0).size();
    System.out.print(get(n, m, arr));
  }
}
 
// This code is contributed by Taranpreet

# Python program for the above approach
 
# Function to find the minimum indexed row
# with maximum unique elements
def get(n, m, v):
    s = set()
     
    # Stores the minimum indexed row
    max_ans = 1000000000
    cnt = -1
    for i in range(0, n):
        for j in range(0, m):
            s.add(v[i][j])
            size = len(s)
            if cnt < size:
                size = cnt
                max_ans = min(max_ans, i)
            s.clear()
    return max_ans
 
if __name__ == "__main__":
    arr = [[1, 2, 3, 4, 5],
           [1, 2, 2, 4, 7],
           [1, 3, 1, 3, 1]]
    n = 3
    m = 5
    print(get(n, m, arr))
 
# This code is contributed by Rohit Pradhan

// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
public class GFG {
 
  // Function to find the minimum indexed row
  // with maximum unique elements
  public static int get(int n, int m, List<List<int>> v) {
    // Stores the unique elements
    HashSet<int> s = new HashSet<int>();
 
    // Stores the minimum indexed row
    int max_ans = int.MaxValue;
    int cnt = -1;
 
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        s.Add(v[i][j]);
      }
      int size = (int) s.Count;
      if (cnt < size) {
        size = cnt;
        max_ans = Math.Min(max_ans, i);
      }
      s.Clear();
    }
    return max_ans;
  }
 
  // Driver Code
  public static void Main(String[] args) {
 
    List<List<int>> arr = new List<List<int>>();
    int [] t1 = {1, 2, 3, 4, 5};
    List<int> temp1 = new List<int>();
    temp1 = (t1.ToList());
    List<int> temp2 = new List<int>();
    int []t2 = {1, 2, 2, 4, 7};
    temp2 = (t2.ToList());
    List<int> temp3 = new List<int>();
    int[] t3 = {1, 3, 1, 3, 1};
    temp3 = t3.ToList();
    arr.Add(temp1);
    arr.Add(temp2);
    arr.Add(temp3);
    int n = arr.Count;
    int m = arr[0].Count;
    Console.Write(get(n, m, arr));
  }
}
 
// This code is contributed by Rajput-Ji

<script>
       // JavaScript code for the above approach
 
       // Function to find the minimum indexed row
       // with maximum unique elements
       function get(n, m, v) {
           // Stores the unique elements
           let s = new Set();
 
           // Stores the minimum indexed row
           let max_ans = Number.MAX_VALUE;
           let cnt = -1;
 
           for (let i = 0; i < n; i++) {
               for (let j = 0; j < m; j++) {
                   s.add(v[i][j]);
               }
               let size = s.size;
               if (cnt < size) {
                   size = cnt;
                   max_ans = Math.min(max_ans, i);
               }
               s.clear();
           }
           return max_ans;
       }
 
       // Driver Code
 
 
       let arr
           = [[1, 2, 3, 4, 5],
           [1, 2, 2, 4, 7],
           [1, 3, 1, 3, 1]];
       let n = arr.length;
       let m = arr[0].length;
       document.write(get(n, m, arr));
 
      // This code is contributed by Potta Lokesh
   </script>

0

Complejidad de tiempo : O(N*M*logM)
Espacio auxiliar : O(M)