K ყველაზე სუსტი მწკრივები მატრიცის Leetcode გადაწყვეტაში


Რთული ტური Easy
ხშირად ეკითხებიან Amazon
Array ორობითი ძებნა

პრობლემის განცხადება

პრობლემის ”K სუსტი რიგები მატრიქსში” მოცემულია ა matrix n მწკრივისა და მ სვეტის. მატრიცა ივსება 0-ით ან 1-ით. ამ მატრიცაში განსაკუთრებული რამ არის ის, რომ ყველა მიემართება თითოეული მწკრივის მარცხენა მხარეს და ყველა ნულოვანი არის მარჯვენა მხარისკენ.

არსებობს წესების ნაკრები თითოეული მწკრივის სიძლიერის გასაზომად.

  1. მწკრივს უფრო მეტი რაოდენობით აქვს მეტი სიმტკიცე.
  2. თუ ჰალსტუხი ხდება, მაშინ მწკრივის უფრო მცირე რიცხვის მქონე მწკრივს ნაკლები სიმტკიცე აქვს.

პრობლემა ითხოვს მატრიქსში სუსტი მწკრივების პოვნას.

მაგალითი

grid = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
[2,0,3]

განმარტება:

  • ნულოვანი მწკრივი -> 2
  • პირველი რიგი-> 4
  • მეორე რიგი-> 1
  • მესამე რიგი-> 2
  • მეოთხე რიგი-> 5

ნულოვანსა და მეოთხე რიგს შორის, მეოთხე უფრო ძლიერია. ასე რომ, რიგები განლაგებულია ყველაზე სუსტიდან ძლიერზე: 2,0,3,1,4.

K სუსტი მწკრივების მიდგომა მატრიცის Leetcode ამოხსნაში

მიდგომის უკეთ გასაგებად მოდით გამოვიყენოთ იგივე მაგალითი უკეთ გასაგებად. დაითვალეთ თითოების რიგი თითოეულ რიგში. მაგრამ როდესაც ამას გავაკეთებთ სრული მწკრივის გავლით, ამას წრფივი დრო დასჭირდება. დროის სირთულის გასაუმჯობესებლად ვიყენებთ ორობით ძიებას, რომ ვიპოვოთ თითოეული მწკრივის პირველი ნულის ინდექსი და ეს ინდექსი იქნება თითოეული მწკრივის ერთეულების რაოდენობა.

ჩვენ გვინდა დალაგება გავაკეთოთ ორი პირობით:

  1. თითოეული მწკრივის რაოდენობა.
  2. თუ ერთეულის რაოდენობა ტოლია, მაშინ მწკრივის ნომერი.

ამ ხრიკის გამოყენებით შეგვიძლია მისი ერთ ცვლადად გადაკეთება. ჩვენ შეგვიძლია შევქმნათ ქულა აღწერიდან დალაგების პირობების შესატყვისი.

მატრიქსში ყველაზე სუსტი მწკრივების Leetcode ამოხსნა

 

ანგარიში = ჯარისკაცები დათვლა * რიგები + მიმდინარე RowIndex

ასე რომ, ჩვენ შეგვიძლია მივიღოთ ჯარისკაცების დათვლა ქულის / რიგების მიხედვით და rowIndex ქულების% რიგების მიხედვით

ახლა ჩვენ დავალაგებთ ქულას და საწყისი კ ქულის ინდექსი იქნება პასუხი.

განხორციელება

C ++ კოდი მატრიქსში ყველაზე სუსტი რიგებისათვის

#include <bits/stdc++.h>
using namespace std; 
 int numOnes( vector<int> row) {
        int lo = 0;
        int hi = row.size();
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (row[mid] == 1)
                lo = mid + 1;
            else
                hi = mid;
        }
        
        return lo;
    }
vector<int> kWeakestRows(vector<vector<int>>& mat, int k)  {
    int rows = mat.size();
    int cols = mat[0].size();

    int score[rows];
    int j;
    for (int i = 0; i < rows; i++) {
         j = numOnes(mat[i]);
        score[i] = j * rows + i;
    }

    sort(score,score+rows);
    vector<int>ans(k);
    for (int i = 0; i < k; i++) {
        ans[i] = score[i] % rows;
    }

    return ans;
}
int main() 
{ 
 vector<vector<int> > arr = { {1,1,0,0,0 }, 
                              { 1,1,1,1,0 }, 
                              { 1,0,0,0,0 },
                              { 1,1,0,0,0 },
                              { 1,1,1,1,1 }}; 
 int k=3;                               
 vector<int>ans=kWeakestRows(arr,k); 
 for(int i=0;i<k;i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
2 0 3

K სუსტი მწკრივების Java- ის კოდი მატრიქსში

import java.util.*;
public class Tutorialcup {
       public static int numOnes(int[] row) {
        int lo = 0;
        int hi = row.length;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (row[mid] == 1)
                lo = mid + 1;
            else
                hi = mid;
        }
        
        return lo;
    }
       public static int[] kWeakestRows(int[][] mat, int k) {
    int rows = mat.length;
    int cols = mat[0].length;

    int[] score = new int[rows];
    int j;
    for (int i = 0; i < rows; i++) {
         j = numOnes(mat[i]);
        score[i] = j * rows + i;
    }

    Arrays.sort(score);
    for (int i = 0; i < k; i++) {
        score[i] = score[i] % rows;
    }

    return Arrays.copyOfRange(score, 0, k);
}
   public static void main(String[] args) {
    int [][] arr ={      {1,1,0,0,0 }, 
                              { 1,1,1,1,0 }, 
                              { 1,0,0,0,0 },
                              { 1,1,0,0,0 },
                              { 1,1,1,1,1 }}; 
        int k=3;                               
        int[]ans=kWeakestRows(arr,k); 
        System.out.println(Arrays.toString(ans));
  }
}
2 0 3

K სუსტი მწკრივების სირთულის ანალიზი მატრიცული Leetcode ხსნარში

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n * logm + nlogn). n * logm არის თითოეული რიგის ერთეულების გამოსათვლელად და n * logn არის დახარისხებისთვის. აქ n არის მწკრივების რიცხვი და m არის სვეტების რაოდენობა.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (n) რადგან ჩვენ ვინახავთ ქულას. აქ n არის მატრიცის მწკრივების რაოდენობა.

ლიტერატურა