Учурдагы сан Leetcode чечиминен канча сан кичине


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon Bloomberg
согуштук тизме Hashing

Маселени билдирүү

Бул маселеде, бизге берилет согуштук тизме. Бул массивдин ар бир элементи үчүн, ошол элементтен кичине элементтердин санын табышыбыз керек.
б.а ар бир i үчүн (0 <= i

мисал

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

Explanation:
Nums [0] = 8 үчүн андан төрт кичинекей сандар бар (1, 2, 2 жана 3).
Nums үчүн [1] = 1 андан кичине сан жок.
Nums [2] = 2 үчүн (1) караганда бир кичинекей сан бар.
Nums [3] = 2 үчүн (1) караганда бир кичинекей сан бар.
Nums [4] = 3 үчүн ага караганда үч кичинекей сандар бар (1, 2 жана 2).

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

Мамиле (Brute Force)

Биз жөн гана ар бир элемент үчүн солдон оңго карай цикл иштете алабыз.
Ар бир элемент үчүн учурдагы санга караганда азыраак элементтердин санын табабыз.
Ошентип, негизинен, биз ар бир элемент үчүн бир тышкы циклди иштетебиз жана ички циклде, бардык массивди өтүп, ар бир элементти учурдагы мааниден кем санайбыз.

Учурдагы сан 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 чечиминен канча сан кичине экендигинин татаалдыгын талдоо

Убакыт татаалдыгы

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 чечиминен канча сан кичине экендигинин татаалдыгын талдоо

Убакыт татаалдыгы

O (max (n, 100)): Убакыттын татаалдыгы O болот (Max (n, 100)), анда n - бул киргизилген массивдин чоңдугу жана 100 алынат, анткени биз 100 өлчөмүндөгү кошумча массивди жасап жатабыз.

Космостун татаалдыгы 

O (1): Биз кошумча 100 санак массивин колдонуп жатабыз, ошондуктан мейкиндиктин татаалдыгы туруктуу.