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

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 블룸버그 게시물에서
알고리즘 배열 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 92

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

이 문제에서 우리는 정렬. 이 배열의 각 요소에 대해 해당 요소보다 작은 요소의 수를 찾아야합니다.
즉, 각 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 인 추가 배열을 사용하므로 공간 복잡도가 일정합니다.

균열 시스템 설계 인터뷰
Translate »
1