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.
Mündəricat
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.
