რამდენი რიცხვია მცირე ვიდრე ამჟამინდელი რიცხვი Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Bloomberg
Array ჰაშინგი

პრობლემის განცხადება

ამ პრობლემის დროს ჩვენ გვეძლევა მასივი. ამ მასივის თითოეული ელემენტისთვის უნდა გავერკვეთ ამ ელემენტზე ნაკლები ელემენტების რაოდენობის შესახებ.
ანუ თითოეული 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

ჯავა პროგრამა

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 ამოხსნა

დროის სირთულე

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-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

ჯავა პროგრამა

#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 ამოხსნა

დროის სირთულე

O (მაქსიმალური (n, 100)): დროის სირთულე იქნება O (მაქს (n, 100)), სადაც n არის შეყვანის მასივის ზომა და 100 მიიღება, რადგან ჩვენ ვქმნით 100 ზომის დამატებით მასივს, რომელიც ასევე განიხილება.

სივრცის სირთულე 

O (1): ჩვენ ვიყენებთ თვლის 100 მასივის დამატებით მასივს, ამიტომ სივრცის სირთულე მუდმივია.