सध्याच्या लेटकोड सोल्यूशनपेक्षा किती क्रमांक छोटे आहेत


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन ब्लूमबर्ग
अरे हॅशिंग

समस्या विधान

या समस्येमध्ये, आम्हाला एक दिले जाते अॅरे. या अ‍ॅरेच्या प्रत्येक घटकासाठी आम्हाला त्या घटकापेक्षा लहान घटकांची संख्या शोधावी लागेल.
उदा. प्रत्येक 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)
संख्यासाठी [4] = 3 त्यापेक्षा तीन लहान संख्या अस्तित्वात आहेत (1, 2 आणि 2)

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

सध्याच्या लेटकोड सोल्यूशनपेक्षा किती संख्या लहान आहेत याबद्दलचे जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन ^ 2): आम्ही प्रत्येक ने n लांबीसाठी नेस्टेड लूप वापरत आहोत. म्हणून वेळ जटिलता ओ (एन ^ 2) असेल.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): उत्तर परत करण्यासाठी आम्ही नुकताच लांबीचा अ‍ॅरे वापरला आहे. याशिवाय आम्ही कोणतीही अतिरिक्त मेमरी वापरली नाही. म्हणून जागेची जटिलता स्थिर आहे.

दृष्टीकोन (ऑप्टिमाइझ केलेले)

जसे आपल्याला माहित आहे की अ‍ॅरे मधील कोणत्याही घटकापेक्षा लहान संख्या ही संख्या -1 च्या संख्येपेक्षा कमी किंवा समान संख्येइतकी आहे.
जसे, अ‍ॅरे मध्ये
1 2 3 4 4 5
5 पेक्षा कमी संख्यांची संख्या 4 पेक्षा कमी किंवा समान संख्यांची संख्या आहे.
तर, जर आपण काही प्रमाणात दिलेल्या अ‍ॅरेमध्ये उपस्थित असलेल्या प्रत्येक घटकाची संख्या संचयित केली तर आपण किती घटक त्यापेक्षा कमी आहेत हे सहजपणे सांगू शकतो.

सध्याच्या लेटकोड सोल्यूशनपेक्षा किती क्रमांक छोटे आहेत

तर, आम्ही १०१ आकाराचे मोजणी ठेवत आहोत. (कारण [०,१००] ही संख्या असू शकते)
गणना अ‍ॅरेची प्रत्येक अनुक्रमणिका मी दिलेल्या अ‍ॅरे मध्ये 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 ची अतिरिक्त अ‍ॅरे बनवित आहोत जी देखील आडवी नाही.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): आम्ही आकार 100 ची मोजणीचा अतिरिक्त अ‍ॅरे वापरत आहोत, जेणेकरून अवकाशातील अवघडपणा स्थिर राहील.