Hündürlüyə görə yenidən qurma

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma ByteDance Facebook google
Görməmiş QueueBaxılıb 20

Sıranın hündürlüyə görə yenidən qurulmasının problemi

Tutaq ki, növbədə dayanan insanların təsadüfi siyahısı var. Hər bir şəxs bir cüt tam rəqəmlə (h, k) təsvir olunur, burada h - insanın boyu, k - hündürlüyü h-dən böyük və ya bərabər olan bu şəxsin qarşısındakı insanların sayı. Yazın alqoritm növbəni yenidən qurmaq.

misal

Input:

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Sıranın hündürlüyə görə yenidən qurulması üçün alqoritm

  1. N sətir və 2 nəfər sütundan ibarət bir vektor “ans” elan edin, burada n insan sayıdır.
  2. Əvvəlcə yalan olaraq qoyulmuş bütün dəyərlərlə n ölçülü bir Boolean vektoru "yoxlama" sıfırlayın, burada yoxlama [i] i-ni doldurub-doldurmadığımızı göstərir.th mövqe və ya deyil.
  3. Verilən massivi azalmayan qaydada çeşidləyin və iki nəfərin hündürlüyü eynidirsə, daha kiçik K olanı birinci gəlir.
  4. İ-də 0-dan n-ə qədər bir döngə işlədin
    • Cari elementimizin hündürlüyündən eyni və ya daha çox hündürlüyə malik insanların sayını sayan bir "say" dəyişənini başlatın.
    • J-də 0-dan n-ə qədər bir döngə işlədin
      • Əgər cari element hələ doldurulmayıbsa və ya hündürlüklə eyni hündürlüyə sahibdirsə [i], onda artırın
      • Əgər sayma dəyəri cari elementin K-dən çox olarsa, bu dövrədən qopun.
    • Ans [j] = people [i] dəyərini yeniləyin.
    • Çekin dəyərini yeniləyin [j] = true çünki jth indi mövqe tutulub.
  5. "Ans" qayıt.

Hündürlüyə görə növbənin yenidən qurulması üçün tətbiqetmə

Hündürlüyə görə növbənin yenidən qurulması üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> reconstructQueue(vector<vector<int>> &people)
{
    int n = people.size();
    vector<vector<int>> ans(n);
    vector<bool> check(n, false);
    sort(people.begin(), people.end());
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        int j = 0;
        while (count < people[i][1])
        {
            if ((!check[j]) or (ans[j][0] == people[i][0]))
            {
                count++;
            }
            j++;
        }
        while (check[j])
        {
            j++;
        }
        ans[j] = people[i];
        check[j] = true;
    }
    return ans;
}
int main()
{
    vector<vector<int>> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
    vector<vector<int>> ans = reconstructQueue(people);
    for (int i = 0; i < ans.size(); i++)
    {
        for (int j = 0; j < ans[i].size(); j++)
        {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
5 0
7 0
5 2
6 1
4 4
7 1

Yüksəkliklə Sıra Yenidənqurma üçün JAVA proqramı

import java.util.*;
public class Main
{
    public static int[][] reconstructQueue(int[][] people)
    {
        int n = people.length;
        int[][] ans=new int[n][2];
        boolean[] check=new boolean[n];
        for(int i=0;i<n;i++)
        {
            check[i]=false;
        }
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return (a[0] - b[0]);
                } else {
                    return (a[1] - b[1]);
                }
            } 
        });
        for (int i = 0; i < n; i++)
        {
            int count = 0;
            int j = 0;
            while (count < people[i][1])
            {
                if ((check[j]==false) || (ans[j][0] == people[i][0]))
                {
                    count++;
                }
                j++;
            }
            while (check[j])
            {
                j++;
            }
            ans[j][0] = people[i][0];
            ans[j][1] = people[i][1];
            check[j] = true;
        }
        return ans;
    }
  public static void main(String[] args) {
      int[][] people={{10, 0}, {2, 0}, {2, 4}, {8, 1}, {2, 2}, {10, 1}};
      int[][] ans=reconstructQueue(people); 
      for (int i = 0; i < ans.length; i++)
      {
            for (int j = 0; j < ans[i].length; j++)
            {
                System.out.print(ans[i][j]+" ");
            }
            System.out.println();
        }
  }
}
2 0 
10 0 
2 2 
8 1 
2 4 
10 1 

Mürəkkəblik

Zaman mürəkkəbliyi

Hər bir insan üçün mövqeyini tapmaq üçün O (n) vaxt lazımdır, belə ki ümumi zaman mürəkkəbliyi O (n ^ 2) -dir.

Kosmik mürəkkəblik

Hər iki ölçüsü də bir "yoxlama" və "ans" massivi götürdük, beləliklə kosmik mürəkkəblik O (n) -dir.

References

Translate »