જમણી બાજુ પર નાના તત્વોની સંખ્યા  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ Google માઈક્રોસોફ્ટ ઓરેકલ ઉબેર
અરે દ્વિસંગી શોધ વિભાજીત અને વિજય સેગમેન્ટ-ટ્રી સોર્ટિંગ

સમસ્યા નિવેદન  

"જમણી બાજુ પર નાના તત્વોની સંખ્યા" સમસ્યામાં, અમે એક આપ્યું છે એરે એ []. નાના તત્વોની સંખ્યા શોધો કે જે દરેક તત્વની જમણી બાજુએ છે.

ઇનપુટ ફોર્મેટ  

પ્રથમ અને એકમાત્ર લાઇન જેમાં પૂર્ણાંક એન.

N અવકાશ-વિભાજિત પૂર્ણાંકોવાળી બીજી લાઇન.

આઉટપુટ ફોર્મેટ  

N અને અવકાશ-વિભાજિત પૂર્ણાંકોવાળી પ્રથમ અને માત્ર એક જ લાઇન જ્યાં ઇથ સ્થાન પર પૂર્ણાંક અનુક્રમણિકા તત્વની જમણી બાજુએ હોય તેવા નાના_ ઘટકોની સંખ્યા સૂચવે છે.

અવરોધ  

  • 1 <= એન <= 10 ^ 5
  • 1 <= એ [હું] <= 10 ^ 5

ઉદાહરણ  

5
4 10 6 2 1
2 3 2 1 0

સમજૂતી: ઉપરના ઉદાહરણમાં, આઉટપુટ એરેમાં નાના_ઉલિમેન્ટ્સની સંખ્યા શામેલ છે જે તેમની જમણી બાજુએ છે.

અભિગમ  

બે એરે મર્જ કરતી વખતે મર્જ સ sortર્ટના વિચારનો ઉપયોગ કરો. જ્યારે ઉચ્ચ અનુક્રમણિકા તત્વ નીચલા અનુક્રમણિકા તત્વ કરતા ઓછું હોય, ત્યારે તે રજૂ કરે છે કે ઉચ્ચ અનુક્રમણિકા તત્વ તે નીચલા અનુક્રમણિકા પછીના બધા તત્વો કરતા નાનો છે કારણ કે ડાબા ભાગ પહેલાથી સortedર્ટ થયેલ છે. તેથી આવશ્યક ગણતરી માટે નીચલા અનુક્રમણિકાના તત્વ પછી બધા તત્વો ઉમેરો.

અમલીકરણ  

સી ++ પ્રોગ્રામ જમણી બાજુના નાના તત્વોની સંખ્યા માટે

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

જમણી બાજુ પર નાના તત્વોની સંખ્યા માટે જાવા પ્રોગ્રામ

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

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (નોલોગ) જ્યાં n આપેલ એરેનું કદ છે. અહીં આપણે મર્જ સ sortર્ટની વિભાવના લાગુ કરીએ છીએ જે અમને સમયની જટિલતાને દૂર કરવા તરફ દોરી જાય છે.

આ પણ જુઓ
એરેમાં કોણનાં ઉત્પાદનો અસ્તિત્વમાં છે તેની ગણતરી કરો

અવકાશ જટિલતા

ઓ (એન) કારણ કે અમે જવાબને સંગ્રહિત કરવા અને દરેક તત્વ પછી પરિણામને અપડેટ કરવા માટે એરે જાહેર કરીએ છીએ.