Քանի թվեր ավելի փոքր են, քան ներկայիս թվերի Leetcode լուծումը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon Bloomberg
Դասավորություն Հեշինգ

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է ան դասավորություն, Այս զանգվածի յուրաքանչյուր տարրի համար մենք պետք է պարզենք այդ տարրից փոքր տարրերի քանակը:
այսինքն յուրաքանչյուր 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]

Մոտեցում (կոպիտ ուժ)

Մենք կարող ենք պարզապես գործարկել օղակ յուրաքանչյուր տարրի համար ՝ սկսած ձախից աջ:
Յուրաքանչյուր տարրի համար մենք կգտնենք տարրերի քանակը, որոնք ընթացիկ թվից փոքր են:
Այսպիսով, ըստ էության, մենք վարում ենք մեկ արտաքին օղակ յուրաքանչյուր տարրի համար և ներքին օղակում, մենք անցնելու ենք ամբողջ զանգվածը `յուրաքանչյուր տարր հաշվելու համար պակաս, քան ընթացիկ արժեքը:

Իրականացում, թե որքան թվեր են փոքր, քան ընթացիկ համարների Leetcode լուծումը

C ++ ծրագիր

#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

Java ծրագիր

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

Բարդության վերլուծություն, թե որքան թվեր են փոքր, քան ընթացիկ համարների Leetcode լուծումը

Timeամանակի բարդություն

O (n ^ 2): Մենք օգտագործում ենք տեղադրված օղակ, յուրաքանչյուրը աշխատում է n երկարության վրա: Ուստի ժամանակի բարդությունը կլինի O (n ^ 2):

Տիեզերական բարդություն 

O (1): Պատասխանը վերադարձնելու համար մենք պարզապես օգտագործել ենք n երկարության զանգված: Սրա կողքին մենք ոչ մի լրացուցիչ հիշողություն չենք օգտագործել: Այսպիսով, տիեզերական բարդությունը մշտական ​​է:

Մոտեցում (օպտիմիզացված)

Քանի որ գիտենք, որ զանգվածի ցանկացած տարրից փոքր թիվը հավասար է այդ թվից 1-ից պակաս կամ հավասար թվի հաշվարկի:
Ինչպես, զանգվածում
1 2 3 4 4 5
5-ից պակաս թվերի հաշվարկը 4-ից պակաս կամ հավասար թվերի քանակ է:
Այսպիսով, եթե ինչ-որ կերպ պահենք տվյալ զանգվածում առկա յուրաքանչյուր տարրի հաշվարկը, ապա հեշտությամբ կարող ենք ասել, որ քանի տարր պակաս է իրենից:

Քանի թվեր ավելի փոքր են, քան ներկայիս թվերի Leetcode լուծումը

Այսպիսով, մենք պահպանում ենք 101 չափի հաշվարկի զանգված (քանի որ թիվը կարող է լինել [0,100] -ի սահմաններում)
Հաշվող զանգվածի յուրաքանչյուր ցուցիչ ես կասեմ տվյալ զանգվածում i թվի առաջացումը:

Այժմ, իմանալու համար, թե քանի թվեր են դիրքում թվից պակաս կամ հավասար, մենք պետք է կիրառենք նախածանցի գումար:
Այսպիսով, մենք գործածելու ենք նախածանցի գումարը հաշվարկի զանգվածի վրա:

Ապա զանգվածի i յուրաքանչյուր տարրի համար այս i- ից պակաս տարրերի քանակը կհամարվի [i-1]:

Այսպիսով, այս մոտեցման մեջ նախ մենք կստեղծենք մեր հաշվարկի զանգվածը:
Այնուհետև այն կվերածենք նախածանցի գումարի:
Այնուհետև մուտքային զանգվածի յուրաքանչյուր տարրի համար մենք կունենանք [num-1] հաշիվ:

Իրականացում, թե որքան թվեր են փոքր, քան ընթացիկ համարների Leetcode լուծումը

C ++ ծրագիր

#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

Java ծրագիր

#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

Բարդության վերլուծություն, թե որքան թվեր են փոքր, քան ընթացիկ համարների Leetcode լուծումը

Timeամանակի բարդություն

O (առավելագույն (n, 100)): Timeամանակի բարդությունը կլինի O (Max (n, 100)), որտեղ n- ը մուտքային զանգվածի չափն է և 100-ը վերցված է, քանի որ մենք պատրաստում ենք 100 չափի լրացուցիչ զանգված, որը նույնպես անցնում է:

Տիեզերական բարդություն 

O (1): Մենք օգտագործում ենք 100 չափի հաշվարկի լրացուցիչ զանգված, ուստի տարածության բարդությունը կայուն է: