Comment calculer combien de nombres sont inférieurs au nombre actuel en php

Vous recevez un tableau nums. Pour chaque élément nums[i], veuillez compter le nombre de tous les nombres plus petits que lui dans le tableau. Comment devez-vous procéder ? Aujourd'hui, l'éditeur présentera la méthode de calcul du nombre de nombres inférieurs au nombre actuel. Vous pouvez vous y référer si vous en avez besoin.

Je vous donne un tableau nums Pour chaque élément nums[i], veuillez compter le nombre de tous les nombres plus petits que lui dans le tableau.

En d'autres termes, pour chaque nums[i] vous devez calculer le nombre de j valides tels que j != i et nums[j] <

Renvoyer la réponse sous forme de tableau.

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

Exemple 2 :

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

Exemple 3 :

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

Conseils :

• 2 <= nums.length < = 500

• 0 < = nums[i] <= 100

Idée de solution 1

Énumérez chaque nombre du tableau, parcourez le tableau et comptez combien de nombres sont plus petits que le nombre actuel

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

Question de solution idée 2 - tableau de fréquences + somme de préfixes

Notez que la plage de valeurs des nombres est [0,100][0,100], vous pouvez donc envisager d'établir un tableau de fréquences cnt[i]cnt[i] pour représenter le nombre de fois le nombre ii apparaît. Ainsi pour le nombre ii, sa réponse : c'est-à-dire la somme du nombre d'occurrences de nombres plus petits que lui, calcule directement la somme cntcnt qui doit parcourir [0,i-1][0,i−1 ], qui nécessite toujours un temps linéaire pour être calculé, mais nous remarquons que la réponse est une somme de préfixes, nous pouvons donc calculer la somme de préfixes sur le tableau cntcnt. Alors la réponse au nombre ii est cnt[i-1]cnt[i−1], et la complexité temporelle du calcul de la réponse est réduite de O(n)O(n) à O(1)O(1).

Le processus final de l'algorithme est le suivant : parcourir les éléments du tableau, mettre à jour le tableau cntcnt, c'est-à-dire cnt[nums[i]]+=1, puis calculer la somme des préfixes du tableau cntcnt, et enfin parcourir les éléments du tableau Pour. le nombre correspondant O(1)O (1) Obtenez simplement la réponse.

Le tri par comptage est un type spécial de tri par compartiment, qui convient généralement aux situations où la longueur des données triées n est beaucoup plus grande que le type k. Par exemple, dans cette question k=101, n=500, voire 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;
    }}

Apprentissage recommandé : Tutoriel vidéo php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!