વર્તમાન સંખ્યા લીટકોડ સોલ્યુશન કરતા કેટલા નંબરો નાના છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન બ્લૂમબર્ગ
અરે હેશિંગ

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

આ સમસ્યામાં, અમને એક આપવામાં આવે છે એરે. આ એરેના દરેક તત્વ માટે, આપણે તે તત્વ કરતા નાના તત્વોની સંખ્યા શોધવા જોઈએ.
દા.ત. દરેક i (0 <= i) માટે

ઉદાહરણ

nums = [8,1,2,2,3]
[4,0,1,1,3]

સમજૂતી:
સંખ્યામાં [0] = 8 ત્યાં તેના કરતા ચાર નાની સંખ્યાઓ અસ્તિત્વમાં છે (1, 2, 2 અને 3)
સંખ્યા માટે [1] = 1 તેના કરતા ઓછી સંખ્યામાં અસ્તિત્વમાં નથી.
સંખ્યાઓ માટે [2] = 2 ત્યાં એક કરતા ઓછી સંખ્યા અસ્તિત્વમાં છે (1).
સંખ્યાઓ માટે [3] = 2 ત્યાં એક કરતા ઓછી સંખ્યા અસ્તિત્વમાં છે (1).
સંખ્યાઓ માટે []] = there તેના કરતા ત્રણ નાની સંખ્યાઓ અસ્તિત્વમાં છે (4, 3 અને 1)

nums = [6,5,4,8]
[2,1,0,3]

અભિગમ (જડ બળ)

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

હાલની સંખ્યા લિટકોડ સોલ્યુશન કરતા કેટલા નંબરો નાના છે તેનો અમલ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    vector<int> ans;

    for(int i=0;i<nums.size();i++)
    {
        int val=nums.at(i),count=0;
        for(int j=0;j<nums.size();j++)
        {
            if(nums.at(j)<val)  count++;
        }
        ans.push_back(count);
    }

    return ans;
}

int main() 
{
    vector<int> nums{ 8 , 1, 2 , 2 , 3 }; 
    vector<int> ans=smallerNumbersThanCurrent(nums);
    
    for(auto val:ans) cout<<val<<" ";
    cout<<endl;
    
    return 0;  
}
4 0 1 1 3

જાવા પ્રોગ્રામ

import java.lang.*;

class Rextester
{  
    public static int[] smallerNumbersThanCurrent(int[] nums) 
    {
        int[]ans=new int[nums.length];

        for(int i=0;i<nums.length;i++)
        {
            int count=0;
            for(int j=0;j<nums.length;j++)
            {
                if(nums[i]>nums[j])   count++;
            }
            ans[i]=count;
        }

        return ans;
    }
    
    public static void main(String args[])
    {
       int[]nums={8,1,2,2,3};  
       int[]ans=smallerNumbersThanCurrent(nums);
        
       for(int num:ans)  
       {
           System.out.print(num+" ");
       }
        
    }
}
4 0 1 1 3

વર્તમાન સંખ્યાના લેટકોડ સોલ્યુશન કરતા કેટલા નંબરો નાના છે તેના માટેના જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (n ^ 2): અમે n ને લંબાઈ માટે ચાલતા નેસ્ડ લૂપનો ઉપયોગ કરી રહ્યા છીએ. તેથી સમય જટિલતા ઓ (n ^ 2) હશે.

અવકાશ જટિલતા 

ઓ (1): જવાબ પાછો આપવા માટે આપણે લંબાઈ n ની એરે વાપરી છે. આની સાથે અમે કોઈ વધારાની મેમરીનો ઉપયોગ કર્યો નથી. તેથી જગ્યા જટિલતા સતત છે.

અભિગમ (timપ્ટિમાઇઝ)

આપણે જાણીએ છીએ કે એરેમાં કોઈપણ તત્વ કરતાં ઓછી સંખ્યા તે સંખ્યા -1 કરતા ઓછી અથવા તેના સમાન સંખ્યાની ગણતરી સમાન છે.
જેમ, એરેમાં
1 2 3 4 4 5
5 કરતા ઓછી સંખ્યાઓની સંખ્યા 4 થી ઓછી અથવા બરાબર સંખ્યાઓની ગણતરી છે.
તેથી, જો આપણે આપેલ એરેમાં હાજર દરેક તત્વની ગણતરીને કોઈક રીતે સંગ્રહિત કરીએ, તો આપણે સરળતાથી કહી શકીએ કે તેના કરતા કેટલા તત્વો ઓછા છે.

વર્તમાન સંખ્યા લીટકોડ સોલ્યુશન કરતા કેટલા નંબરો નાના છે

તેથી, અમે કદ 101 ની ગણતરીની એરે રાખી રહ્યા છીએ. (કારણ કે સંખ્યા [0,100] ની વચ્ચે હોઈ શકે છે)
ગણતરી એરેનો દરેક અનુક્રમણિકા હું આપેલ એરેમાં નંબરની ઘટના કહીશ.

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

પછી એરેના દરેક તત્વ i માટે, આ સંખ્યા કરતા ઓછા તત્વોની સંખ્યા ગણતરી કરવામાં આવશે [i-1].

તેથી, આ અભિગમમાં સૌ પ્રથમ આપણે આપણી ગણતરી એરે બનાવીશું.
પછી આપણે તેને પ્રીફિક્સ સરવાળોમાં કન્વર્ટ કરીશું.
પછી ઇનપુટ એરેના દરેક ઘટક સંખ્યા માટે આપણી પાસે ગણતરી હશે [num-1].

હાલની સંખ્યા લિટકોડ સોલ્યુશન કરતા કેટલા નંબરો નાના છે તેનો અમલ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    int count[101];
    memset(count,0,sizeof(count));
    for(auto& i:nums)
    {
        count[i]++;
    }

    for(int i=1;i<=100;i++)
    {
        count[i]=count[i-1]+count[i];
    }

    vector<int> ans;

    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]==0)    ans.push_back(0);
        else    ans.push_back(count[nums[i]-1]);
    }

    return ans;
}

int main() 
{
    vector<int> nums{ 8 , 1, 2 , 2 , 3 }; 
    vector<int> ans=smallerNumbersThanCurrent(nums);
    
    for(auto val:ans) cout<<val<<" ";
    cout<<endl;
    
    return 0;  
}
4 0 1 1 3

જાવા પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    int count[101];
    memset(count,0,sizeof(count));
    for(auto& i:nums)
    {
        count[i]++;
    }

    for(int i=1;i<=100;i++)
    {
        count[i]=count[i-1]+count[i];
    }

    vector<int> ans;

    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]==0)    ans.push_back(0);
        else    ans.push_back(count[nums[i]-1]);
    }

    return ans;
}

int main() 
{
    vector<int> nums{ 8 , 1, 2 , 2 , 3 }; 
    vector<int> ans=smallerNumbersThanCurrent(nums);
    
    for(auto val:ans) cout<<val<<" ";
    cout<<endl;
    
    return 0;  
}
4 0 1 1 3

વર્તમાન સંખ્યાના લેટકોડ સોલ્યુશન કરતા કેટલા નંબરો નાના છે તેના માટેના જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (મહત્તમ (એન, 100)): સમય જટિલતા ઓ (મેક્સ (એન, 100)) હશે જ્યાં એન ઇનપુટ એરેનું કદ છે અને 100 લેવામાં આવે છે કારણ કે આપણે કદ 100 ની વધારાની એરે બનાવી રહ્યા છીએ જે પણ ટ્ર traવર્સ થઈ ગઈ છે.

અવકાશ જટિલતા 

ઓ (1): અમે કદ 100 ની ગણતરીઓના વધારાના એરેનો ઉપયોગ કરી રહ્યાં છીએ, તેથી અવકાશ જટિલતા સતત.