ప్రస్తుత సంఖ్య లీట్‌కోడ్ పరిష్కారం కంటే ఎన్ని సంఖ్యలు చిన్నవి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ బ్లూమ్బెర్గ్
అర్రే హ్యాషింగ్

విషయ సూచిక

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు ఒక ఇవ్వబడుతుంది అమరిక. ఈ శ్రేణి యొక్క ప్రతి మూలకం కోసం, ఆ మూలకం కంటే చిన్న మూలకాల సంఖ్యను మనం కనుగొనాలి.
అంటే ప్రతి 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

ప్రస్తుత సంఖ్య లీట్‌కోడ్ పరిష్కారం కంటే ఎన్ని సంఖ్యలు చిన్నవిగా ఉన్నాయో సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (n ^ 2): మేము n పొడవు కోసం నడుస్తున్న ప్రతి ఒక్కటి సమూహ లూప్‌ను ఉపయోగిస్తున్నాము. అందువల్ల సమయ సంక్లిష్టత O (n ^ 2) అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): మేము జవాబును తిరిగి ఇవ్వడానికి పొడవు n యొక్క శ్రేణిని ఉపయోగించాము. దీని పక్కన మేము అదనపు మెమరీని ఉపయోగించలేదు. కాబట్టి స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.

అప్రోచ్ (ఆప్టిమైజ్ చేయబడింది)

శ్రేణిలోని ఏ మూలకం కంటే చిన్న సంఖ్య ఆ సంఖ్య -1 కంటే తక్కువ లేదా సమానమైన సంఖ్యకు సమానమని మనకు తెలుసు.
ఇష్టం, శ్రేణిలో
1 2 3 4 4 5
5 కన్నా తక్కువ సంఖ్యల సంఖ్య 4 కంటే తక్కువ లేదా సమానమైన సంఖ్యల సంఖ్య.
కాబట్టి, ఇచ్చిన శ్రేణిలో ఉన్న ప్రతి మూలకం యొక్క గణనను మనం ఏదో ఒకవిధంగా నిల్వ చేస్తే, దాని కంటే ఎన్ని మూలకాలు తక్కువగా ఉన్నాయో మనం సులభంగా చెప్పగలం.

ప్రస్తుత సంఖ్య లీట్‌కోడ్ పరిష్కారం కంటే ఎన్ని సంఖ్యలు చిన్నవి

కాబట్టి, మేము పరిమాణం 101 యొక్క గణన శ్రేణిని ఉంచుతున్నాము. (ఎందుకంటే ఈ సంఖ్య [0,100] మధ్య ఉండవచ్చు)
కౌంట్ అర్రే యొక్క ప్రతి సూచిక నేను ఇచ్చిన శ్రేణిలో సంఖ్య i యొక్క సంభవనీయతను చెబుతాను.

ఇప్పుడు, ఒక స్థానం వద్ద ఎన్ని సంఖ్యలు తక్కువ లేదా సమానంగా ఉన్నాయో తెలుసుకోవడానికి, మేము ఉపసర్గ మొత్తాన్ని వర్తింపజేయాలి.
కాబట్టి, మేము కౌంట్ అర్రేలో ఉపసర్గ మొత్తాన్ని వర్తింపజేస్తాము.

అప్పుడు శ్రేణి యొక్క ప్రతి మూలకం కోసం, ఈ సంఖ్య కంటే తక్కువ మూలకాల సంఖ్య లెక్కించబడుతుంది [i-1].

కాబట్టి, ఈ విధానంలో మొదట మన కౌంట్ శ్రేణిని సృష్టిస్తాము.
అప్పుడు మేము దానిని ఉపసర్గ మొత్తంగా మారుస్తాము.
ఇన్పుట్ శ్రేణి యొక్క ప్రతి మూలకం సంఖ్యకు మనకు గణన ఉంటుంది [సంఖ్యా -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

ప్రస్తుత సంఖ్య లీట్‌కోడ్ పరిష్కారం కంటే ఎన్ని సంఖ్యలు చిన్నవిగా ఉన్నాయో సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (గరిష్టంగా (n, 100%): సమయ సంక్లిష్టత O (గరిష్టంగా (n, 100%) ఉంటుంది, ఇక్కడ n అనేది ఇన్పుట్ శ్రేణి యొక్క పరిమాణం మరియు 100 తీసుకోబడుతుంది ఎందుకంటే మేము పరిమాణం 100 యొక్క అదనపు శ్రేణిని తయారు చేస్తున్నాము, అది కూడా అడ్డంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): మేము పరిమాణం 100 యొక్క అదనపు శ్రేణిని ఉపయోగిస్తున్నాము, కాబట్టి స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.