오른쪽의 더 작은 요소 수

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 구글 Microsoft 신탁 동네 짱
배열 이진 검색 분열과 정복 세그먼트 트리 정렬조회수 383

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“우측에있는 더 작은 요소의 수”문제에서 우리는 정렬 ㅏ[]. 각 요소의 right_side에있는 더 작은 요소의 수를 찾으십시오.

입력 형식

정수 N을 포함하는 첫 번째이자 유일한 행입니다.

N 개의 공백으로 구분 된 정수를 포함하는 두 번째 줄.

출력 형식

n 개의 공백으로 구분 된 정수를 포함하는 첫 번째 및 유일한 행입니다. 여기서 i 번째 위치의 정수는 인덱스 요소의 오른쪽에있는 small_elements의 수를 나타냅니다.

제약

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

5
4 10 6 2 1
2 3 2 1 0

설명 : 위의 예에서 출력 배열은 오른쪽에있는 small_elements의 수를 포함합니다.

접근

두 배열을 병합 할 때 병합 정렬 개념을 사용하십시오. 상위 인덱스 요소가 하위 인덱스 요소보다 작 으면 왼쪽 부분이 이미 정렬되어 있으므로 상위 인덱스 요소가 하위 인덱스 이후의 모든 요소보다 작음을 나타냅니다. 따라서 필요한 개수에 대해 하위 인덱스 요소 뒤에있는 모든 요소를 ​​더합니다.

실시

오른쪽에있는 더 작은 요소 수를위한 C ++ 프로그램

#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<<" ";
    }
}

오른쪽의 작은 요소 수를위한 Java 프로그램

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

복잡성 분석

시간 복잡성

O (nlogn) 어디에 n 주어진 배열의 크기입니다. 여기서 우리는 nlogn 시간 복잡성으로 이끄는 병합 정렬 개념을 적용합니다.

공간 복잡성

O (N) 답을 저장할 배열을 선언하고 각 요소 다음에 결과를 업데이트하기 때문입니다.

균열 시스템 설계 인터뷰
Translate »