K- ի ամենաթույլ շարքերը մատրիցային Leetcode լուծման մեջ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
Դասավորություն Երկուական որոնում

Խնդրի հայտարարություն

«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]

Բացատրությունը.

  • Zeroth շարքը -> 2
  • Առաջին շարք-> 4
  • Երկրորդ շարք-> 1
  • Երրորդ շարք-> 2
  • Չորրորդ շարք-> 5

Erրոտի և չորրորդ շարքի միջև չորրորդն ավելի ուժեղ է: Այսպիսով շարքերը դասավորված են ամենաթույլից ուժեղ: 2,0,3,1,4:

The K Weakest Rows- ի մոտեցումը մատրիցային Leetcode լուծման մեջ

Մոտեցումն ավելի լավ հասկանալու համար օգտագործենք նույն օրինակն ավելի լավ հասկանալու համար: Հաշվի՛ր յուրաքանչյուր շարքում դրանց քանակը: Բայց երբ մենք դա անենք ամբողջական տողանցքով անցնելիս, դա գծային ժամանակ կպահանջի: Այսպիսով, ժամանակի բարդությունը բարելավելու համար մենք կօգտագործենք երկուական որոնում `յուրաքանչյուր տողի առաջին զրոյի ինդեքսը գտնելու համար, և այդ ցուցանիշը կլինի յուրաքանչյուր տողի նորերի քանակը:

Մենք ուզում ենք տեսակավորում կատարել ըստ երկու պայմանի.

  1. Յուրաքանչյուր շարքում դրանց քանակը:
  2. Եթե ​​դրանց թիվը հավասար է, ապա տողի համարը:

Մենք կարող ենք այն փոխել մեկ փոփոխականի այս հնարքի միջոցով: մենք կարող ենք ստեղծել հաշիվ նկարագրության տեսակավորման պայմանին համապատասխանելու համար:

Մատրիցայի կ ամենաթույլ շարքերում Leetcode լուծում

 

հաշիվ = զինվորներՀաշիվ * տողեր + ընթացիկՍարքիԻնդեքս

Այսպիսով, մենք կարող ենք զինվորներՀաշվել ըստ հաշիվի / տողերի, իսկ rowIndex- ը `ըստ% տողերի գնահատման:

Այժմ մենք տեսակավորելու ենք հաշիվը և պատասխան կլինի մեկնարկային k միավորի ինդեքսը:

Իրականացման

C ++ ծածկագիրը մատրիցայի K ամենաթույլ շարքերում

#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

Java- ի կոդը մատրիցայում K ամենաթույլ շարքերի համար

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 լուծման մեջ

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n * logm + nlogn), n * logm- ը յուրաքանչյուր շարքում մեկի թիվը հաշվարկելու համար է, իսկ n * logn- ը `տեսակավորելու համար: Այստեղ n- ը շարքերի քանակն է, իսկ m- ը ՝ սյունակների քանակը:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է O (n) քանի որ մենք հաշիվն ենք պահում: Այստեղ n - մատրիցում տողերի քանակն է:

Սայլակ