Одоогийн тооны Leetcode шийдлээс хэдэн тоо бага байна


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Bloomberg
Array Хаширч байна

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд массив. Энэ массивын элемент бүрийн хувьд бид тухайн элементээс цөөн тооны элементийн тоог олох ёстой.
өөрөөр хэлбэл i (0 <= i

Жишээ нь

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

Тайлбар:
Nums [0] = 8-ийн хувьд үүнээс 1 жижиг тоо байдаг (2, 2, 3 ба XNUMX).
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 дугаарын тохиолдлыг хэлэх болно.

Одоо хэдэн байрлал дээр байгаа тооноос цөөн буюу түүнтэй тэнцүү тоог мэдэхийн тулд нийлбэрийн угтварыг хэрэглэх ёстой.
Тиймээс тооллын массив дээр sum гэсэн угтварыг хэрэглэнэ.

Дараа нь массивын 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 (хамгийн их (n, 100)): Цаг хугацааны нарийн төвөгтэй байдал нь O (Max (n, 100)) байх бөгөөд n нь оролтын массивын хэмжээ бөгөөд 100-ыг нэмж 100 массив хийж байгаа тул XNUMX-г авна.

Сансрын нарийн төвөгтэй байдал 

O (1): Бид 100 хэмжээтэй нэмэлт тооллогыг ашиглаж байгаа тул орон зайн нарийн төвөгтэй байдал тогтмол байна.