ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಿಂತ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳು ಚಿಕ್ಕದಾಗಿದೆ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಬ್ಲೂಮ್ಬರ್ಗ್
ಅರೇ ಹ್ಯಾಶಿಂಗ್

ಪರಿವಿಡಿ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಸರಣಿ. ಈ ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ, ಆ ಅಂಶಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು.
ಅಂದರೆ ಪ್ರತಿ 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]

ಅಪ್ರೋಚ್ (ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ)

ಎಡದಿಂದ ಬಲಕ್ಕೆ ಪ್ರಾರಂಭಿಸಿ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ನಾವು ಲೂಪ್ ಅನ್ನು ಸರಳವಾಗಿ ಚಲಾಯಿಸಬಹುದು.
ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ, ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಗಿಂತ ಕಡಿಮೆ ಇರುವ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಕಾಣುತ್ತೇವೆ.
ಆದ್ದರಿಂದ ಮೂಲಭೂತವಾಗಿ, ನಾವು ಪ್ರತಿ ಅಂಶಕ್ಕೆ ಒಂದು ಹೊರಗಿನ ಲೂಪ್ ಅನ್ನು ಓಡಿಸುತ್ತೇವೆ ಮತ್ತು ಆಂತರಿಕ ಲೂಪ್‌ನಲ್ಲಿ, ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಪ್ರಸ್ತುತ ಮೌಲ್ಯಕ್ಕಿಂತ ಕಡಿಮೆ ಎಣಿಸಲು ನಾವು ಇಡೀ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ.

ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಿಂತ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳು ಚಿಕ್ಕದಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಿಂತ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳು ಚಿಕ್ಕದಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಸಂಕೀರ್ಣತೆಯ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ ^ 2): ನಾವು n ಉದ್ದಕ್ಕಾಗಿ ಚಾಲನೆಯಲ್ಲಿರುವ ನೆಸ್ಟೆಡ್ ಲೂಪ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (n ^ 2) ಆಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (1): ಉತ್ತರವನ್ನು ಹಿಂತಿರುಗಿಸಲು ನಾವು ಉದ್ದ n ನ ಶ್ರೇಣಿಯನ್ನು ಬಳಸಿದ್ದೇವೆ. ಇದರ ಪಕ್ಕದಲ್ಲಿ ನಾವು ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿಯನ್ನು ಬಳಸಿಲ್ಲ. ಆದ್ದರಿಂದ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.

ಅಪ್ರೋಚ್ (ಆಪ್ಟಿಮೈಸ್ಡ್)

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಯಾವುದೇ ಅಂಶಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಸಂಖ್ಯೆ ಆ ಸಂಖ್ಯೆ -1 ಕ್ಕಿಂತ ಕಡಿಮೆ ಅಥವಾ ಸಮನಾದ ಸಂಖ್ಯೆಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ.
ರಚನೆಯಲ್ಲಿ ಲೈಕ್ ಮಾಡಿ
1 2 3 4 4 5
5 ಕ್ಕಿಂತ ಕಡಿಮೆ ಇರುವ ಸಂಖ್ಯೆಗಳ ಎಣಿಕೆ 4 ಕ್ಕಿಂತ ಕಡಿಮೆ ಅಥವಾ ಸಮನಾದ ಸಂಖ್ಯೆಗಳ ಎಣಿಕೆ.
ಆದ್ದರಿಂದ, ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಅಂಶಗಳ ಎಣಿಕೆಯನ್ನು ನಾವು ಹೇಗಾದರೂ ಸಂಗ್ರಹಿಸಿದರೆ, ಅದಕ್ಕಿಂತ ಎಷ್ಟು ಅಂಶಗಳು ಕಡಿಮೆ ಎಂದು ನಾವು ಸುಲಭವಾಗಿ ಹೇಳಬಹುದು.

ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಿಂತ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳು ಚಿಕ್ಕದಾಗಿದೆ

ಆದ್ದರಿಂದ, ನಾವು 101 ಗಾತ್ರದ ಎಣಿಕೆ ಶ್ರೇಣಿಯನ್ನು ಇರಿಸುತ್ತಿದ್ದೇವೆ. (ಏಕೆಂದರೆ ಈ ಸಂಖ್ಯೆ [0,100] ನಡುವೆ ಇರಬಹುದು)
ಎಣಿಕೆ ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಸೂಚ್ಯಂಕವು ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಸಂಖ್ಯೆ i ನ ಸಂಭವವನ್ನು ನಾನು ಹೇಳುತ್ತೇನೆ.

ಈಗ, ಒಂದು ಸ್ಥಾನದಲ್ಲಿ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳು ಕಡಿಮೆ ಅಥವಾ ಸಮನಾಗಿವೆ ಎಂದು ತಿಳಿಯಲು, ನಾವು ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತವನ್ನು ಅನ್ವಯಿಸಬೇಕು.
ಆದ್ದರಿಂದ, ನಾವು ಎಣಿಕೆ ರಚನೆಯಲ್ಲಿ ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತವನ್ನು ಅನ್ವಯಿಸುತ್ತೇವೆ.

ನಂತರ ರಚನೆಯ ಪ್ರತಿ ಅಂಶಕ್ಕೆ, ಈ ಸಂಖ್ಯೆಗಿಂತ ಕಡಿಮೆ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಲಾಗುತ್ತದೆ [i-1].

ಆದ್ದರಿಂದ, ಈ ವಿಧಾನದಲ್ಲಿ ಮೊದಲು ನಾವು ನಮ್ಮ ಎಣಿಕೆ ರಚನೆಯನ್ನು ರಚಿಸುತ್ತೇವೆ.
ನಂತರ ನಾವು ಅದನ್ನು ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತವಾಗಿ ಪರಿವರ್ತಿಸುತ್ತೇವೆ.
ನಂತರ ಇನ್ಪುಟ್ ರಚನೆಯ ಪ್ರತಿ ಅಂಶ ಸಂಖ್ಯೆಗೆ ನಾವು ಎಣಿಕೆ [ಸಂಖ್ಯೆ -1] ಅನ್ನು ಹೊಂದಿರುತ್ತೇವೆ.

ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಿಂತ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳು ಚಿಕ್ಕದಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಿಂತ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳು ಚಿಕ್ಕದಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಸಂಕೀರ್ಣತೆಯ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಗರಿಷ್ಠ (ಎನ್, 100)): ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಒ (ಮ್ಯಾಕ್ಸ್ (ಎನ್, 100) ಆಗಿರುತ್ತದೆ, ಅಲ್ಲಿ n ಎಂಬುದು ಇನ್ಪುಟ್ ಅರೇನ ಗಾತ್ರವಾಗಿದೆ ಮತ್ತು 100 ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ನಾವು ಹೆಚ್ಚುವರಿ ಗಾತ್ರದ 100 ಶ್ರೇಣಿಯನ್ನು ತಯಾರಿಸುತ್ತಿದ್ದೇವೆ ಮತ್ತು ಅದು ಹಾದುಹೋಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (1): ನಾವು ಗಾತ್ರದ 100 ಎಣಿಕೆಗಳ ಹೆಚ್ಚುವರಿ ಶ್ರೇಣಿಯನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ, ಆದ್ದರಿಂದ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.