አሁን ካለው ቁጥር ምን ያህል ቁጥሮች ያነሱ ናቸው Leetcode መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ብሉምበርግ
ሰልፍ ሃምሽንግ

የችግሩ መግለጫ

በዚህ ችግር ውስጥ እኛ አንድ ተሰጠን ደርድር. ለእያንዳንዱ የዚህ ድርድር አካል ፣ ከዚያ ንጥረ ነገር ያነሱ ንጥረ ነገሮችን ቁጥር መፈለግ አለብን።
ማለትም ለእያንዳንዱ እኔ (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]

አቀራረብ (የጭካኔ ኃይል)

ከግራ ወደ ቀኝ በመጀመር በቀላሉ ለእያንዳንዱ አካል አንድ ዙር ማካሄድ እንችላለን።
ለእያንዳንዱ ንጥረ ነገር ከአሁኑ ቁጥር ያነሱ ንጥረ ነገሮችን ብዛት እናገኛለን ፡፡
ስለዚህ በመሰረታዊነት ፣ ለእያንዳንዱ ንጥረ ነገር አንድ የውጭ ዑደት እናደርጋለን እና በውስጠኛው ዑደት ውስጥ ፣ እያንዳንዱን ንጥረ ነገር ከአሁኑ እሴት በታች ለመቁጠር መላውን ድርድር እናቋርጣለን ፡፡

አሁን ካለው ቁጥር ሌቲኮድ መፍትሔው ስንት ቁጥሮች ያነሱ ናቸው የሚለው ትግበራ

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

አሁን ካለው ቁጥር ሌቲኮድ መፍትሔው ስንት ቁጥሮች ያነሱ እንደሆኑ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n ^ 2) እያንዳንዳችን ለ n ርዝመቶች የሚሮጡ የጎጆ ጥብሶችን እንጠቀማለን ፡፡ ስለዚህ የጊዜ ውስብስብነት O (n ^ 2) ይሆናል።

የቦታ ውስብስብነት 

ኦ (1) መልሱን ለመመለስ የ n ንዝመት ድርድርን አሁን ተጠቅመናል ፡፡ ከዚህ ጎን ለጎን ምንም ተጨማሪ ማህደረ ትውስታ አልተጠቀምንም ፡፡ ስለዚህ የቦታ ውስብስብነት ቋሚ ነው።

አቀራረብ (የተመቻቸ)

በአንድ ድርድር ውስጥ ከማንኛውም ንጥረ ነገር ያነሰ ቁጥሩ ከቁጥር ያነሰ ወይም ከዚያ ቁጥር ጋር እኩል ነው -1.
እንደ ድርድር
1 2 3 4 4 5
የቁጥር ብዛት ከ 5 በታች ቁጥሮች ከ 4 ያነሱ ወይም እኩል ናቸው።
ስለዚህ ፣ በተጠቀሰው ድርድር ውስጥ የሚገኙትን እያንዳንዱን ንጥረ-ነገር በሆነ መንገድ ብናስቀምጥ ከዚያ ምን ያህል ንጥረ ነገሮች ከእሱ ያነሱ እንደሆኑ በቀላሉ መናገር እንችላለን ፡፡

አሁን ካለው ቁጥር ምን ያህል ቁጥሮች ያነሱ ናቸው Leetcode መፍትሔ

ስለዚህ ፣ እኛ ቁጥር 101 የሆነ የቁጥር ድርድርን እንጠብቃለን (ምክንያቱም ቁጥሩ በ [0,100] መካከል ሊሆን ይችላል)
እያንዳንዱ የቁጥር ድርድር መረጃ በተጠቀሰው ድርድር ውስጥ እኔ ቁጥር መ መከሰት እላለሁ።

አሁን በአንድ ቦታ ላይ ከአንድ ቁጥር ጋር ምን ያህል ቁጥሮች እንደሚያንሱ ወይም እንደሚያነሱ ለማወቅ ፣ ቅድመ ቅጥያ ድምርን ማመልከት አለብን ፡፡
ስለዚህ ፣ በቁጥር ድርድር ላይ የቅድመ ቅጥያ ድምርን ተግባራዊ እናደርጋለን።

ከዚያ ለእያንዳንዱ የድርጅት i ክፍል ፣ ከዚህ ቁጥር ያነሱ ንጥረ ነገሮች ቁጥር ይቆጠራሉ [i-1]።

ስለዚህ በዚህ አካሄድ በመጀመሪያ የእኛን የቁጥር ድርድር እንፈጥራለን ፡፡
ከዚያ ወደ ቅድመ ቅጥያ ድምር እንለውጠዋለን ፡፡
ከዚያ ለእያንዳንዱ የግብዓት ድርድር ቁጥር የቁጥር ቁጥር (ቁጥር -1) ይኖረናል።

አሁን ካለው ቁጥር ሌቲኮድ መፍትሔው ስንት ቁጥሮች ያነሱ ናቸው የሚለው ትግበራ

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

አሁን ካለው ቁጥር ሌቲኮድ መፍትሔው ስንት ቁጥሮች ያነሱ እንደሆኑ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ከፍተኛ (n ፣ 100)) የጊዜ ውስብስብነት O (ማክስ (n ፣ 100)) ይሆናል n በግብዓት ድርድር መጠን እና 100 በሚወሰድበት ምክንያቱም እኛ ደግሞ ተሻግረን የምንሄድበት የ 100 መጠን ተጨማሪ ድርድር ስለምናደርግ ነው

የቦታ ውስብስብነት 

ኦ (1) እኛ የምንጠቀምበት ተጨማሪ ብዛት ያላቸው የቁጥር ብዛት ብዛት 100 ነው ፣ ስለሆነም የቦታ ውስብስብነት ቋሚ ነው።