차례
문제 정책
이 문제에서 우리는 정렬. 이 배열의 각 요소에 대해 해당 요소보다 작은 요소의 수를 찾아야합니다.
즉, 각 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보다 작거나 같은 숫자의 개수입니다.
따라서 주어진 배열에있는 모든 요소의 개수를 어떻게 든 저장하면 얼마나 많은 요소가 그보다 적은지 쉽게 말할 수 있습니다.
그래서 우리는 크기 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 인 추가 배열을 사용하므로 공간 복잡도가 일정합니다.
