PHP 를 이용 하여 현재 숫자 보다 작은 숫자 를 계산 하 는 방법 예시
다시 말 하면 모든 nums[i]에 대해 효과 적 인 j 의 수량 을 계산 해 야 합 니 다.그 중에서 j 는 j 를 만족 시 켜 야 합 니 다!=i.그리고 nums[j]
예시 1:
입력:nums=[8,1,2,2,3]
출력:[4,0,1,1,3]
설명:
nums[0]=8 에는 그것 보다 작은 네 개의 숫자 가 존재 한다.(1,2,2,3).
nums[1]=1 에 대해 서 는 그것 보다 작은 숫자 가 존재 하지 않 습 니 다.
nums[2]=2 에 대해 서 는 그것 보다 작은 숫자 가 존재 합 니 다:(1).
nums[3]=2 에 대해 서 는 그것 보다 작은 숫자 가 존재 합 니 다:(1).
nums[4]=3 에는 그것 보다 작은 숫자 세 개가 존재 합 니 다.(1,2,2)
예시 2:
입력:nums=[6,5,4,8]
출력:[2,1,0,3]
예시 3:
입력:nums=[7,7,7,7]
출력:[0,0,0,0,0]
알림:
사고 풀이 1
매 거 진 배열 의 모든 숫자 는 배열 을 옮 겨 다 니 며 현재 숫자 보다 몇 개의 숫자 가 작 으 면 됩 니까?
코드
class Solution {
/** * @param Integer[] $nums * @return Integer[] */
function smallerNumbersThanCurrent($nums) {
$count = count($nums);
$result = array_fill(0, $count, 0);
for ($i = 0; $i < $count; $i++) {
for ($j = 0; $j < $count; $j++) {
if ($nums[$j] < $nums[$i]) {
$result[$i]++;
}
}
}
return $result;
}
}
숫자의 값 영역 범 위 는[0,100][0,100]임 을 알 수 있 기 때문에 주파수 배열 cnt[i]cnt[i]를 구축 하여 숫자 ii 가 나타 난 횟수 를 나타 내 는 것 을 고려 할 수 있다.그러면 숫자 ii 에 있어 서 그 답 은 그 숫자 보다 작은 숫자 가 나타 나 는 개수 의 합 이다.직접 계산 하려 면[0,i-1][0,i-1]의 cntcnt 구 화 를 옮 겨 다 니 며 선형 시간 을 계산 해 야 한다.그러나 우 리 는 이 답 이 접두사 와 접두사 라 는 것 을 알 았 기 때문에 cntcnt 배열 에 접두사 와 접 두 사 를 구 할 수 있 습 니 다.그렇다면 숫자 ii 에 대한 답 은 cnt[i-1]cnt[i-1]이다.답 을 계산 하 는 시간 복잡 도 는 O(n)O(n)에서 O(1)O(1)로 떨 어 졌 다.
마지막 으로 전체 알고리즘 절 차 는 배열 요 소 를 옮 겨 다 니 며 cntcnt 배열,즉 cnct[nums[i]+1 을 업데이트 한 다음 cntcnt 배열 에 접두사 와 마지막 으로 배열 요 소 를 옮 겨 다 니 며 해당 하 는 숫자 O(1)O(1)에 대해 답 을 얻 으 면 됩 니 다.
계수 정렬 은 특수 한 통 정렬 으로 정렬 데이터 길이 n 이 종류 k 보다 훨씬 큰 경우 에 적용 된다.예 를 들 어 본 문제 k=101,n=500,심지어 5000.
코드
class Solution {
/** * @param Integer[] $nums * @return Integer[] */
function smallerNumbersThanCurrent($nums) {
$count = count($nums);
$cnt = array_fill(0, 101, 0); // 0
$result = array_fill(0, $count, 0); // 0
// $nums $cnt
foreach ($nums as $num) {
$cnt[$num]++;
}
// $cnt $i sum($cnt[0], .. $cnt[$i - 1]) ， $i
foreach (range(1, 100) as $i) {
$cnt[$i] += $cnt[$i - 1];
}
//
foreach (range(0, $count - 1) as $i) {
if ($nums[$i]) {
$result[$i] = $cnt[$nums[$i] - 1];
}
}
return $result;
}
}
leetcode 공식 문제 풀이
총결산
PHP 를 이용 하여 현재 숫자 보다 작은 숫자 를 계산 하 는 이 글 을 소개 합 니 다.더 많은 관련 PHP 계산 이 현재 숫자 보다 작은 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Laravel - 변환된 유효성 검사 규칙으로 API 요청 제공동적 콘텐츠를 위해 API를 통해 Laravel CMS에 연결하는 모바일 앱(또는 웹사이트) 구축을 고려하십시오. 이제 앱은 CMS에서 번역된 콘텐츠를 받을 것으로 예상되는 다국어 앱이 될 수 있습니다. 일반적으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
