How to calculate how many numbers are less than the current number in php-PHP Problem-php.cn

How to calculate how many numbers are less than the current number in php

醉折花枝作酒筹

Release： 2023-03-11 11:02:01

forward

2270 people have browsed it

Give you an array nums. For each element nums[i], please count the number of all numbers smaller than it in the array. How should you do it? Today, the editor will introduce the method of calculating how many numbers are smaller than the current number. You can refer to it if you need it.

How to calculate how many numbers are less than the current number in php

Given you an array nums, for each element nums[i], please count the number of all numbers smaller than it in the array.

In other words, for each nums[i] you must calculate the number of valid j such that j != i and nums[j] < nums[i] .

Return the answer as an array.

Example 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）。

Copy after login

Example 2:

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

Copy after login

Example 3:

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

Copy after login

Tip:

2 <= nums.length <= 500
##0 <= nums[i] < ;= 100

Solution idea 1

Enumerate each number in the array, traverse the array and count how many numbers are smaller than the current number Just

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

Copy after login

Solution idea 2 - Frequency array prefix and

Notice that the value range of numbers is [0,100][0,100 ], so you can consider establishing a frequency array cnt[i]cnt[i] to represent the number of times the number ii appears. Then for the number ii, its answer: that is, the sum of the number of occurrences of numbers smaller than it, directly calculates the need Traversing the cntcnt sum of [0,i-1][0,i−1] still requires linear time to calculate, but we note that the answer is a prefix sum, so we can then calculate the prefix sum of the cntcnt array. Then the answer to the number ii is cnt[i-1]cnt[i−1], and the time complexity of calculating the answer is reduced from O(n)O(n) to O(1)O(1).

The final entire algorithm process is: traverse the array elements, update the cntcnt array, that is, cnt[nums[i]] =1, then calculate the prefix sum of the cntcnt array, and finally traverse the array elements. For the corresponding number O( 1)O(1) Just get the answer.

Counting sorting is a special kind of bucket sorting, which is generally suitable for situations where the sorted data length n is much larger than the type k. For example, in this question k=101, n=500, or even 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;
    }}

Copy after login

Recommended learning:

php video tutorial

The above is the detailed content of How to calculate how many numbers are less than the current number in php. For more information, please follow other related articles on the PHP Chinese website!