Sıralanmış Matrisdəki K-ci Kiçik Element

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

In Sıralanmış Matrisdəki K-ci element problem, hər sətrin və sütunun azalmayan qaydada sıralandığı bir nxn matrisini verdik. Verilən 2D massivindəki k ən kiçik elementi tapın.

misal

Input 1:
k = 3 and 
matrix =
        11, 21, 31, 41
        16, 26, 36, 46
        25, 30, 38, 49
        33, 34, 40, 50
Ouput: 21
Explanation: The 3rd smallest element = 21 


Input 2:
k = 7 and 
matrix =
        12, 23, 31
        17, 27, 36
        24, 29, 38
Ouput: 31
Explanation: The 7th smallest element is 30

Sıralanmış Matrisdəki K-ci Kiçik Element üçün Həllin növləri

Sadəlövh / Gücün Gücü
min Heap məlumat quruluşundan istifadə etmək
İkili axtarış

Sadəlövh / Gücün Gücü

Yanaşma

Bu yanaşma, sadəcə matrisin bütün elementlərini birinə əlavə etməyi nəzərdə tutur array, massivi çeşidləmək və k-ci ən kiçik ədədi qaytarmaq.

Sıralanmış Matrisdəki K-ci Kiçik Element üçün Alqoritm

bir matris verilmişdir mat [] [] ölçüləri nxn, xətti bir sıra yaradın arr [] ölçüsü n * n.
Bütün elementlərini əlavə edin Qida daxil arr.
Arrı sıralayın və arr [return k-1] (k-ci ən böyük element).

Sıralanmış Matritsada K-ci Kiçik Element üçün tətbiqetmə

C ++ Proqramı

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find k-th largest element
int kthSmallest(vector < vector<int> > mat,int k)
{
    int n = mat.size();
    
    if(k > n*n)
    return -1;
    
    // smallest element is the first element of the matrix
    if(k == 1)
    return mat[0][0];
    
    // define array and push contents of the matrix into it
    vector <int> arr;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        arr.push_back(mat[i][j]);
    
    // sort the array and obtain k-th smallest element
    sort(arr.begin(),arr.end());
    
    return arr[k-1];
}

int main() 
{
  vector< vector<int> > mat {
                              {11, 21, 31, 41},
                              {16, 26, 36, 46},
                              {25, 30, 38, 49},
                              {33, 34, 40, 50}
                              };
  
  int k = 3;
  int kthsmall = kthSmallest(mat,k);
  
    if(kthsmall == -1)
    cout<<"3rd smallest element doesn't exist.";
    else
    cout<<"3rd smallest element = "<<kthsmall<<endl;
  
  return 0;
}

3rd smallest element = 21

Java Proqramı

import java.io.*;
import java.util.*;

class tutorialCup 
{
    // function to find k-th largest element
    static int kthSmallest(ArrayList<ArrayList<Integer>> mat,int k)
    {
        int n = mat.size();
        
        if(k > n*n)
        return -1;
        
        // smallest element is the first element of the matrix
        if(k == 1)
        return mat.get(0).get(0);
        
        // define array and push contents of the matrix into it
        ArrayList <Integer> arr = new ArrayList <Integer>();
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            arr.add(mat.get(i).get(j));
        
        // sort the array and obtain k-th smallest element
        Collections.sort(arr);
        
        return arr.get(k-1);
    }

    public static void main (String[] args) 
    {
    	ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();
    	mat.add(new ArrayList<Integer>(Arrays.asList(11, 21, 31, 41)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(16, 26, 36, 46)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(25, 30, 38, 49)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(33, 34, 40, 50)));
    	                            
    	int k = 3;
    	int kthsmall = kthSmallest(mat,k);
    	
        if(kthsmall == -1)
        System.out.println("3rd smallest element doesn't exist.");
        else
        System.out.println("3rd smallest element = "+kthsmall);
    	
    }    
}

3rd smallest element = 21

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi: T (n) = O (n²)
Kosmik Mürəkkəblik: A (n) = O (n²)

Min Heap data strukturundan istifadə

Yanaşma

matrisin birinci sətrinin elementlərini, sonra yığından bir-bir pop elementini saxlamaq və son atılan elementin dərhal altında yatan matrisdən elementi əlavə etmək üçün yığın məlumat quruluşundan (prioritet növbə / dəq yığın) istifadə edirik. Bu, k-addımlar k-ci ən böyük ədədi əldə edənə qədər edilir. The alqoritm aşağıda müzakirə olunur:

Sıralanmış Matrisdəki K-ci Kiçik Element üçün Alqoritm

əsas işlərlə açıq şəkildə məşğul olmaq (n = 0,1).
min yığını müəyyənləşdirin pq.
ilk sətirdən elementləri əlavə edin mat [] [] (giriş matrisi) pq.
İndi k-dəfə bir döngə işlədin. loop dəyişəndir i, bu loopun içərisində aşağıdakı addımları yerinə yetirin:
- bir elementi açın pq və atılmış elementi içəridə saxlayın kthsmall
- içində yatan elementi əlavə edin mat [] [] yalnız aşağıda kiçik daxil pq.
Döngə bitdikdən sonra saxlanılan son element dəyərini qaytarın kiçik (yəni kthsmall.num).

PinPin

Sıralanmış Matritsada K-ci Kiçik Element üçün tətbiqetmə

C ++ Proqramı

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// define a strucure 
// to store a particular value from the matrix
// it's row and column number
struct element
{
    int num;
    int i;
    int j;
    
    // define constructors
    element(){}
    element(int element,int rownum,int colnum)
    {
        num = element;
        i = rownum;
        j = colnum;
    }
};

// this is an strucure which implements the 
// operator overlading 
// this will help us in creating a heap for storing
// values of element(struct) data type
struct compare 
{ 
    bool operator()(element const& p1, element const& p2) 
    { 
        return p1.num > p2.num; 
    } 
}; 

// function to find k-th largest element
int kthSmallest(vector < vector<int> > mat,int k)
{
    int n = mat.size();
    
    if(k > n*n)
    return -1;
    
    // smallest element is the first element of the matrix
    if(k == 1)
    return mat[0][0];
    
    // define a min Heap
    priority_queue <struct element,vector <element>,compare > pq;
    
    // push all the elements of first row
    // along with their row and column numbers
    // into a min heap
    for(int i=0;i<n;i++)
    {
        struct element curr(mat[0][i],0,i);
        pq.push(curr);
    }
    
    // define a variable to process each value stored in min heap
    struct element kthsmall;
    
    // pop from heap for k steps
    for(int i=0;i<k;i++)
    {
        kthsmall = pq.top();
        pq.pop();
        
        // if last popped element lies in the last row\
        // dont need to push any number
        if(kthsmall.i+1 >= n)
        {
            struct element curr(INT_MAX,-1,-1);
            pq.push(curr);
        }
        /* push the element below (element in the same column as the element itself)
        the last element popped from the minheap*/ 
        else
        {
            struct element curr(mat[kthsmall.i + 1][kthsmall.j],kthsmall.i+1,kthsmall.j);
            pq.push(curr);
        }
    }
    
    // return the element last popped from the heap pq
    return kthsmall.num;
    
}

int main() 
{
  vector< vector<int> > mat {
                              {11, 21, 31, 41},
                              {16, 26, 36, 46},
                              {25, 30, 38, 49},
                              {33, 34, 40, 50}
                              };
  
  int k = 3;
  int kthsmall = kthSmallest(mat,k);
  
    if(kthsmall == -1)
    cout<<"3rd smallest element doesn't exist.";
    else
    cout<<"3rd smallest element = "<<kthsmall<<endl;
  
  return 0;
}

3rd smallest element = 21

Java Proqramı

import java.io.*;
import java.util.*;

/*
define a strucure 
to store a particular value from the matrix
it's row and column number
*/
public class element
{
    public int num;
    public int i;
    public int j;
    
    public element(){}
    
    public element(int element,int rownum,int colnum)
    {
        num = element;
        i = rownum;
        j = colnum;
    }
    
    public int numReturn()
    {
        return num;
    }
}

class tutorialCup 
{
    // function to find k-th largest element
    static int kthSmallest(ArrayList<ArrayList<Integer>> mat,int k)
    {
        int n = mat.size();
    
        if(k > n*n)
        return -1;
        
        // smallest element is the first element of the matrix
        if(k == 1)
        return mat.get(0).get(0);
        
        // Comparator forms heap using num attribute of object of element type
        // sorts the heap using obj.num value
        // where obj is an object of element type
        Comparator<element> sorter = Comparator.comparing(element::numReturn);
        // define a min Heap
        PriorityQueue <element> pq = new PriorityQueue<element>(sorter);
        
        // push all the elements of first row
        // along with their row and column numbers
        // into a min heap
        for(int i=0;i<n;i++)
        {
            element curr = new element(mat.get(0).get(i),0,i);
            pq.add(curr);
        }
        
        // define a variable to process each value stored in min heap
        element kthsmall = new element();
        
        // pop from heap for k steps
        for(int i=0;i<k;i++)
        {
            kthsmall = pq.peek();
            pq.poll();
            
            // if last popped element lies in the last row\
            // dont need to push any number
            if(kthsmall.i+1 >= n)
            {
                element curr = new element(Integer.MAX_VALUE,-1,-1);
                pq.add(curr);
            }
            /* push the element below (element in the same column as the element itself)
            the last element popped from the minheap*/ 
            else
            {
                element curr = new element(mat.get(kthsmall.i + 1).get(kthsmall.j),kthsmall.i+1,kthsmall.j);
                pq.add(curr);
            }
        }
    
        // return the element last popped from the heap pq
        return kthsmall.num;
    }

    public static void main (String[] args) 
    {
    	ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();
    	mat.add(new ArrayList<Integer>(Arrays.asList(11, 21, 31, 41)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(16, 26, 36, 46)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(25, 30, 38, 49)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(33, 34, 40, 50)));
    	                            
    	int k = 3;
    	int kthsmall = kthSmallest(mat,k);
    	
        if(kthsmall == -1)
        System.out.println("3rd smallest element doesn't exist.");
        else
        System.out.println("3rd smallest element = "+kthsmall);
    	
    }    
}

3rd smallest element = 21

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: T (n) = O (n + klogn)
Kosmik Mürəkkəblik: A (n) = O (n)

İkili axtarış

Yanaşma

Matris matına ikili axtarış tətbiq edə bilərik [] [], lakin bu şərti ikili axtarışdan fərqlidir, çünki bu vəziyyətdə “indeks aralığı” əvəzinə “say aralığı” (matris dəyərlərinin özü) hesab edirik. Matrisimizin ən kiçik sayının sol üst küncdə, ən böyük rəqəmin aşağı alt küncdə olduğunu bildiyimiz kimi. Bu iki rəqəm “aralığı”, yəni lo və hi ikili axtarış üçün dəyərlər. aşağıda alqoritmimizi necə tətbiq etdiyimizi izah edirik.

Sıralanmış Matrisdəki K-ci Kiçik Element üçün Alqoritm

İkili başlayın axtarış ilə lo = mat[0][0] və hi = mat[n-1][n-1].
Tapmaq mid Bu lo və hi. Bu middle sayı mütləq matrisdəki bir element deyildir.
Bütün rəqəmləri kiçik və ya bərabər sayın mid matrisdə. Matris çeşidləndiyindən bunu O (N) -də edə bilərik.
Sayı 'K' -dən azdırsa, yeniləyə bilərik lo = mid+1 matrisin yuxarı hissəsində axtarış aparmaq
Əks halda, sayma 'K' -dən böyük və ya bərabərdirsə, yeniləyə bilərik hi = mid növbəti təkrarlamada matrisin aşağı hissəsində axtarış etmək.
Bir anda lo və hi dəyərlərdə bərabərləşir və döngə sona çatır. lo axtarış aralığımızı tək bir matris elementinə qədər təkrarladığımız üçün k-ci elementin dəyərini ehtiva edir.

Sıralanmış Matritsada K-ci Kiçik Element üçün tətbiqetmə

C ++ Proqramı

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find k-th largest element
int kthSmallest(vector < vector<int> > mat,int k)
{
    int n = mat.size();
        
    if(k == 0 || k > n*n || n == 0)
    return -1;
    
    if(k == 1)
    return mat[0][0];
    
    // define smallest and largest element in the matrix as
    // lower range &
    // upper range
    int lo = mat[0][0];
    int hi = mat[n-1][n-1];
    
    // perform binary search (by value)
    // between smallest(top-left) and largest(bottom-down) values
    while (lo < hi) 
    {
        int mid = lo + (hi - lo) / 2;
        int count = 0;
        int j = n - 1;
        
        // find out how many numbers are greater than mid
        // between lo and hi
        for (int i = 0; i < n; i++) 
        {
            while (j >= 0 && mat[i][j] > mid) 
                j--;
                
            count += (j + 1);
        }
        
        // if number of such element is less than k
        // narrow the search range by increasing lo value
        if (count < k) 
            lo = mid + 1;
        // if number of such element is greater or equal to k
        // narrow the search range by decreasing hi value
        else 
            hi = mid;
    } 
    
    // after iteratively narrowing the search range
    // you narrow down to a single element in the matrix
    // which is k-th smallest element
    return lo;
}

int main() 
{
  vector< vector<int> > mat {
                              {11, 21, 31, 41},
                              {16, 26, 36, 46},
                              {25, 30, 38, 49},
                              {33, 34, 40, 50}
                              };
  
  int k = 3;
  int kthsmall = kthSmallest(mat,k);
  
    if(kthsmall == -1)
    cout<<"3rd smallest element doesn't exist.";
    else
    cout<<"3rd smallest element = "<<kthsmall<<endl;
  
  return 0;
}

3rd smallest element = 21

Java Proqramı

import java.io.*;
import java.util.*;

class tutorialCup 
{
    // function to find k-th largest element
    // this function performs a binary search by value
    // on the given matrix
    static int kthSmallest(ArrayList<ArrayList<Integer>> mat,int k)
    {
        int n = mat.size();
        
        if(k == 0 || k > n*n || n == 0)
        return -1;
        
        if(k == 1)
        return mat.get(0).get(0);
        
        // define smallest and largest element in the matrix as
        // lower range &
        // upper range
        int lo = mat.get(0).get(0);
        int hi = mat.get(n-1).get(n-1);
        
        // perform binary search (by value)
        // between smallest(top-left) and largest(bottom-down) values
        while (lo < hi) 
        {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            int j = n - 1;
            
            // find out how many numbers are greater than mid
            // between lo and hi
            for (int i = 0; i < n; i++) 
            {
                while (j >= 0 && mat.get(i).get(j) > mid) 
                    j--;
                    
                count += (j + 1);
            }
            
            // if number of such element is less than k
            // narrow the search range by increasing lo value
            if (count < k) 
                lo = mid + 1;
            // if number of such element is greater or equal to k
            // narrow the search range by decreasing hi value
            else 
                hi = mid;
        } 
        
        // after iteratively narrowing the search range
        // you narrow down to a single element in the matrix
        // which is k-th smallest element
        return lo;
    }

    public static void main (String[] args) 
    {
    	ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();
    	mat.add(new ArrayList<Integer>(Arrays.asList(11, 21, 31, 41)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(16, 26, 36, 46)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(25, 30, 38, 49)));
    	mat.add(new ArrayList<Integer>(Arrays.asList(33, 34, 40, 50)));
    	                            
    	int k = 3;
    	int kthsmall = kthSmallest(mat,k);
    	
        if(kthsmall == -1)
        System.out.println("3rd smallest element doesn't exist.");
        else
        System.out.println("3rd smallest element = "+kthsmall);
    	
    }    
}

3rd smallest element = 21

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi: T (n) = O (nlog (max-min)) = O (nlog (const)) = O (n), burada max-min, matrisdəki ən böyük və ən kiçik dəyərlər arasındakı fərqdir. Hər ikisi də tam ədədlər, maksimum fərq INT_MAX-dən çox ola bilməz, buna görə mahiyyətcə max-min sabit olur.
Kosmik Mürəkkəblik: A (n) = O (1)

References

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr