Bir Matris Leetcode həllində K Zəif Sətirlər

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

Problem bəyanat

Problemdə ”Bir Matrisdəki K Zəif Sətirlər” bizə verilir matris n sətir və m sütununun. matris 0 və ya 1 ilə doldurulur. Bu matrisin xüsusiyyəti odur ki, hamısı hər sətrin sol tərəfinə, bütün sıfırlar isə sağ tərəfə tərəfdir.

Hər sətrin gücünü ölçmək üçün bir sıra qaydalar mövcuddur.

Daha çox sayda sıra daha çox gücə malikdir.
Qalereya meydana gəlsə, daha kiçik bir sıra nömrəsi olan sıra daha az gücə malikdir.

Problem bir matrisdəki ən zəif satırları tapmağı xahiş edir.

misal

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]

Explanation:

Zeroth sıra -> 2
Birinci sıra -> 4
İkinci sıra -> 1
Üçüncü sıra-> 2
Dördüncü sıra -> 5

Sıfır və dördüncü sıra arasında dördüncüsü daha güclüdür. Beləliklə, cərgələr ən zəifdən güclüə doğru sıralanırdı: 2,0,3,1,4.

Bir Matrix Leetcode həllində K Zəif Sətirlərin yanaşması

Yanaşmanı daha yaxşı başa düşmək üçün daha yaxşı başa düşmək üçün eyni nümunədən istifadə edək. Hər sətirdə olanların sayını sayın. Ancaq bunu bütün cərgəni keçərək edəcəyik zaman xətti vaxt aparacaq. Zaman mürəkkəbliyini yaxşılaşdırmaq üçün hər sətirdə ilk sıfırın indeksini tapmaq üçün ikili axtarışdan istifadə edəcəyik və bu indeks hər sətirdə olanların sayı olacaqdır.

İki şərtə görə çeşidləmə etmək istəyirik:

Hər sətirdə olanların sayı.
Birinin sayı bərabərdirsə, sıra nömrəsi.

Bu hiylədən istifadə edərək onu bir dəyişənə çevirə bilərik. təsvirdən sort vəziyyətinə uyğun bir hesab yarada bilərik.

hesab = əsgərlərin sayı * satırlar + currentRowIndex

Beləliklə, əsgər sayını hesab / sətirlə əldə edə bilərik və% sətirdə rowIndex əldə edə bilərik.

İndi hesabı çeşidləyəcəyik və başlanğıc k hesabının indeksi cavab olacaq.

Həyata keçirilməsi

Matrisdəki K Zəif Sətirlər üçün C ++ kodu

#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

Matrisdəki K Zəif Sətirlər üçün Java kodu

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