השורות K החלשות ביותר בפתרון Leetcode של מטריקס


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית
מערך חיפוש בינארי

הצהרת בעיה

בבעיה "השורות K החלשות ביותר במטריקס" ניתן לנו מַטרִיצָה של n שורות ו- m עמודות. המטריצה ​​מתמלאת ב- 0 או 1. הדבר המיוחד במטריקס זה הוא שכל אלה נמצאים לצד שמאל של כל שורה וכל האפסים הם כלפי הצד הימני.

יש סט כללים למדידת חוזק כל שורה.

  1. לשורה עם מספרים רבים יותר יש כוח גדול יותר.
  2. אם השוויון מתרחש אז לשורה עם מספר שורה קטן יותר יש פחות כוח.

הבעיה מבקשת למצוא את השורות החלשות ביותר k במטריצה.

דוגמה

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 לשורות K החלשות במטריצה

 

ציון = חיילים ספירה * שורות + CurrentRowIndex

כדי שנוכל להשיג חיילים לספור לפי ציון / שורות ולקבל 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 מטריקס

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n * logm + nlogn). n * logm מיועד לחישוב מספר אלה בכל שורה ו- n * logn מיועד למיון. כאן n הוא מספר השורות ו- m הוא מספר העמודות.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (n) כי אנחנו שומרים את הציון. כאן n הוא מספר השורות במטריצה.

הפניות