현재 숫자 Leetcode 솔루션보다 작은 숫자의 수


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 블룸버그
배열 해싱

문제 정책

이 문제에서 우리는 정렬. 이 배열의 각 요소에 대해 해당 요소보다 작은 요소의 수를 찾아야합니다.
즉, 각 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 및 XNUMX)가 있습니다.

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

접근 (Brute Force)

왼쪽에서 오른쪽으로 모든 요소에 대해 간단히 루프를 실행할 수 있습니다.
각 요소에 대해 현재 숫자보다 적은 요소의 개수를 찾습니다.
따라서 기본적으로 각 요소에 대해 하나의 외부 루프를 실행하고 내부 루프에서 전체 배열을 탐색하여 현재 값보다 작은 모든 요소를 ​​계산합니다.

현재 Number 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

현재 Number Leetcode 솔루션보다 작은 수에 대한 복잡성 분석

시간 복잡성

O (n ^ 2) : 우리는 각각 n 개의 길이로 실행되는 중첩 루프를 사용하고 있습니다. 따라서 시간 복잡도는 O (n ^ 2)가됩니다.

공간 복잡성 

O (1) : 우리는 답을 반환하기 위해 길이 n의 배열을 사용했습니다. 이 외에도 추가 메모리를 사용하지 않았습니다. 따라서 공간 복잡성은 일정합니다.

접근 방식 (최적화)

우리가 알고 있듯이 배열의 어떤 요소보다 작은 숫자는 해당 숫자 1보다 작거나 같은 숫자의 개수와 같습니다.
처럼, 배열
1 2 3 4 4 5
5보다 작은 숫자의 개수는 4보다 작거나 같은 숫자의 개수입니다.
따라서 주어진 배열에있는 모든 요소의 개수를 어떻게 든 저장하면 얼마나 많은 요소가 그보다 적은지 쉽게 말할 수 있습니다.

현재 숫자 Leetcode 솔루션보다 작은 숫자의 수

그래서 우리는 크기 101의 count 배열을 유지합니다. (숫자가 [0,100] 사이 일 수 있기 때문입니다)
카운트 배열 i의 모든 인덱스는 주어진 배열에서 숫자 i의 발생을 말합니다.

이제 한 위치에서 숫자보다 작거나 같은 숫자의 수를 알기 위해 접두사 합계를 적용해야합니다.
따라서 count 배열에 접두사 합계를 적용합니다.

그러면 배열의 각 요소 i에 대해이 숫자보다 작은 요소의 수가 count [i-1]이됩니다.

따라서이 접근 방식에서는 먼저 count 배열을 만듭니다.
그런 다음 접두사 합계로 변환합니다.
그런 다음 입력 배열의 각 요소 수에 대해 count [num-1]을 갖게됩니다.

현재 Number 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

현재 Number Leetcode 솔루션보다 작은 수에 대한 복잡성 분석

시간 복잡성

O (최대 (n, 100)) : 시간 복잡도는 O (Max (n, 100))이 될 것입니다. 여기서 n은 입력 배열의 크기이고 100은 크기가 100 인 추가 배열을 만들고 있기 때문입니다.

공간 복잡성 

O (1) : 크기가 100 인 추가 배열을 사용하므로 공간 복잡도가 일정합니다.