Матрицалык Leetcode чечиминдеги K Алсыз саптар  


Кыйынчылык деңгээли жеңил
Көп суралган Amazon
Алгоритмы согуштук тизме Binary Search коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions

Көйгөйдү айтуу  

"Матрицанын эң начар саптары" көйгөйүндө бизге а Булакта n катарлардын жана m мамылардын. матрица 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]

Explanation:

  • Zeroth катар -> 2
  • Биринчи катар-> 4
  • Экинчи катар-> 1
  • Үчүнчү катар-> 2
  • Төртүнчү катар-> 5

Нөл менен төртүнчү катардын ортосунда төртүнчүсү күчтүү. Ошентип, катарлар алсыздан күчтүүгө чейин жайгашты: 2,0,3,1,4.

Матрицалык Leetcode Чечиминдеги K Алсыз Катарлардын жакындап келиши  

Бул ыкманы жакшыраак түшүнүү үчүн, жакшыраак түшүнүү үчүн ушул эле мисалды келтирели. Ар бир катардагы бирөөнүн санын санап чыгыңыз. Бирок биз муну толук катардан өтүп, сызыктуу убакытты талап кылат. Ошентип, убакыттын татаалдыгын жакшыртуу үчүн экилик издөөнү колдонуп, ар бир катардагы биринчи нөлдүн индексин табабыз жана ал индекс ар бир саптагы бир катар болот.

ошондой эле
Римге бүтүн сан

Биз сорттоону эки шарт боюнча жүргүзгүбүз келет:

  1. Ар бир катардагы саны.
  2. Эгер алардын саны барабар болсо, анда катар номери.

Ушул трюкту колдонуп, биз аны бир өзгөрмөгө айланта алабыз. сыпаттамадан сорттоо шартына дал келген упай түзө алабыз.

Матрицанын эң начар катарларына Leetcode чечимитөөнөч

 

упай = soldierCount * катарлар + currentRowIndex

Ошентип, аскерлерди эсептөө упайлары / саптары боюнча, ал эми% катарлары менен rowIndex алабыз.

Эми биз упайларды иреттейбиз жана баштапкы к баллдын индекси жооп берет.

ишке ашыруу

Матрицанын K Алсыз Катарлары үчүн 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

Матрицалык Leetcode эритмесиндеги K Алсыз саптардын татаалдыгын талдоо  

Убакыттын татаалдыгы

Жогорудагы коддун убакыттын татаалдыгы O (n * logm + nlogn). n * logm - ар бир катардагы бирөөнүн санын эсептөө үчүн, n * logn - сорттоо үчүн. Бул жерде n - катарлардын, m - мамылардын саны.

ошондой эле
Студенттердин катышуусун эсепке алуу I Leetcode Solution

Космостун татаалдыгы

Жогорудагы коддун мейкиндик татаалдыгы O (N) анткени биз эсепти сактап жатабыз. Бул жерде n - матрицанын катарларынын саны.

шилтемелер