PHP에서 현재 숫자보다 작은 숫자의 수를 계산하는 방법

nums라는 배열이 주어졌습니다. 각 요소 nums[i]에 대해 배열에서 그보다 작은 모든 숫자의 수를 세어보세요. 오늘은 편집자가 현재 숫자보다 작은 숫자가 몇 개인지 계산하는 방법을 소개하겠습니다. 필요하시면 참고하시면 됩니다.

각 요소 nums[i]에 대해 배열에서 그보다 작은 모든 숫자의 수를 세어보세요.

즉, 각 nums[i]에 대해 j != i 및 nums[j] < nums[i] 와 같은 유효한 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]

팁:

• 2 <= nums.length <= 5 00

• 0 < = nums[i] <= 100

해결 방법 아이디어 1

배열의 각 숫자를 열거하고, 배열을 순회하며 현재 숫자보다 작은 숫자의 개수를 세어보세요.

Code

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;
    }}

해결 방법 질문 아이디어 2 - 주파수 배열 + 접두어 합

숫자의 값 범위는 [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 배열, 즉 cnt[nums[i]]+=1을 업데이트한 다음 cntcnt 배열의 접두어 합계를 계산하고 마지막으로 배열 요소를 순회하는 것입니다. 해당 숫자 O(1)O (1) 그냥 답을 얻으세요.

카운팅 정렬은 특별한 종류의 버킷 정렬로, 일반적으로 정렬된 데이터 길이 n이 k 유형보다 훨씬 큰 상황에 적합합니다. 예를 들어, 이 질문에서는 k=101, n=500, 심지어 5000입니다.

Code

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;
    }}

추천 학습: php 비디오 튜토리얼

위 내용은 PHP에서 현재 숫자보다 작은 숫자의 수를 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!