Sağ tərəfdəki kiçik elementlərin sayı

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg google microsoft Kahin Über
Geyim İkili axtarış Bölün və fəth edin Seqment ağacı çeşidləyiciBaxılıb 383

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“Sağ tərəfdəki Kiçik Elementlərin Sayı” problemində bir array a []. Hər bir elementin sağ tərəfində olan kiçik elementlərin sayını tapın.

Giriş Formatı

Bir tam ədədi olan ilk və yalnız bir sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

Boşluqla ayrılmış n tam ədədi ehtiva edən ilk və yalnız bir sətir, burada ith mövqesindəki tam ədədin indeks elementinin sağ tərəfində olan kiçik_elementlərin sayını göstərir.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 5
  • 1 <= a [i] <= 10 ^ 5

misal

5
4 10 6 2 1
2 3 2 1 0

Explanation: Yuxarıdakı nümunədə, çıxış massivində sağ tərəfdə olan kiçik_elementlərin sayı göstərilir.

Yanaşma

İki massivin birləşməsi zamanı birləşmə növü fikrindən istifadə edin. Daha yüksək indeks elementi aşağı indeks elementindən az olduqda, yuxarı hissə elementinin həmin alt indeksdən sonra bütün elementlərdən kiçik olduğunu göstərir, çünki sol hissə artıq sıralanmışdır. Beləliklə, tələb olunan sayım üçün aşağı indeks elementindən sonra bütün elementləri əlavə edin.

Həyata keçirilməsi

Sağ tərəfdə kiçik elementlərin sayı üçün C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
vector<int> res;
    
void mergeSort(vector<int>& nums, int l, int r, vector<int>& tmp, vector<int>& index) 
{
        if (l >= r) return;
        int m = l + (r - l) / 2; 
        mergeSort(nums, l, m, tmp, index); 
        mergeSort(nums, m + 1, r, tmp, index); 
        int i = l, j = m + 1, k = l; int count = 0; 
        while (i <= m) 
        {
            while (j <= r && nums[index[j]] < nums[index[i]]) 
            {
                count++;
                tmp[k++] = index[j++];
            } 
            res[index[i]] += count;
            tmp[k++] = index[i++];
        }
        while(j<=r) 
        {
            tmp[k++] = index[j++];
        }
        for(i=l;i<=r;i++) 
        {
            index[i] = tmp[i];
        }
}

vector<int> countSmaller(vector<int>& nums) 
{
    res.resize(nums.size()); 
    vector<int> tmp(nums.size(), 0);
    vector<int> index; 
    for(int i = 0; i < nums.size(); i++) 
    {
        index.push_back(i);
    }
    mergeSort(nums, 0, nums.size() - 1, tmp, index);
    return res;
}

int main()
{
    int n;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
    }
    vector<int> res = countSmaller(v);
    for(auto x: res)
    {
        cout<<x<<" ";
    }
}

Sağ tərəfdə kiçik elementlərin sayı üçün Java proqramı

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static void update(int num, int fen[]) 
    {
        for(int i=num; i<=20001; i+=(i&-i)) 
            fen[i] += 1;
    }
    public static int find(int num, int fen[]) 
    {
        int ans = 0;
        for(int i=num; i>0; i-=(i&-i)) 
            ans += fen[i];
        return ans;
    }
    public  static void countSmaller(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        int fen[] = new int[20002];
        for(int i=n-1; i>=0; i--) 
        {
            ans[i] = find(10000 + nums[i] - 1, fen);
            update(10000 + nums[i], fen);
        }
        for(int i = 0; i < n; i++)
        {
            System.out.print(ans[i]+" ");
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        List<Integer> v = new ArrayList<Integer>() {};
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        countSmaller(a);
    }
}
9
1 4 2 7 2 4 221 54 23
0 2 0 2 0 0 2 1 0

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (nlogn) hara n verilmiş massivin ölçüsüdür. Burada bizi nlogn zaman mürəkkəbliyinə aparan birləşmə növü konsepsiyasını tətbiq edirik.

Kosmik Mürəkkəblik

O (n) çünki cavabı saxlamaq və nəticəni hər elementdən sonra yeniləmək üçün bir sıra elan edirik.

Crack Sistemi Dizayn Müsahibələri
Translate »