php怎么計算多少數字小于當前數字

這篇文章主要講解了“php怎么計算多少數字小于當前數字”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“php怎么計算多少數字小于當前數字”吧！

給你一個數組 nums，對于其中每個元素 nums[i]，請你統計數組中比它小的所有數字的數目。

換而言之，對于每個 nums[i] 你必須計算出有效的 j 的數量，其中 j 滿足 j != i 且 nums[j] < nums[i] 。

以數組形式返回答案。

示例 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 <= 500

• 0 <= nums[i] <= 100

解題思路 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;
    }}

解題思路 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。

代碼

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怎么計算多少數字小于當前數字這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！