php怎么計(jì)算多少數(shù)字小于當(dāng)前數(shù)字

這篇文章主要講解了“php怎么計(jì)算多少數(shù)字小于當(dāng)前數(shù)字”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“php怎么計(jì)算多少數(shù)字小于當(dāng)前數(shù)字”吧！

創(chuàng)新互聯(lián)建站專注于香坊網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。熱誠(chéng)為您提供香坊營(yíng)銷型網(wǎng)站建設(shè)，香坊網(wǎng)站制作、香坊網(wǎng)頁(yè)設(shè)計(jì)、香坊網(wǎng)站官網(wǎng)定制、小程序設(shè)計(jì)服務(wù)，打造香坊網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供香坊網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

給你一個(gè)數(shù)組 nums，對(duì)于其中每個(gè)元素 nums[i]，請(qǐng)你統(tǒng)計(jì)數(shù)組中比它小的所有數(shù)字的數(shù)目。

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

以數(shù)組形式返回答案。

示例 1：

輸入：nums = [8,1,2,2,3]
輸出：[4,0,1,1,3]
解釋： 
對(duì)于 nums[0]=8 存在四個(gè)比它小的數(shù)字：（1，2，2 和 3）。 
對(duì)于 nums[1]=1 不存在比它小的數(shù)字。
對(duì)于 nums[2]=2 存在一個(gè)比它小的數(shù)字：（1）。 
對(duì)于 nums[3]=2 存在一個(gè)比它小的數(shù)字：（1）。 
對(duì)于 nums[4]=3 存在三個(gè)比它小的數(shù)字：（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

枚舉數(shù)組里的每個(gè)數(shù)字，遍歷數(shù)組統(tǒng)計(jì)有多少數(shù)字比當(dāng)前數(shù)字小即可

代碼

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 - 頻次數(shù)組+前綴和

注意到數(shù)字的值域范圍為 [0,100][0,100] ，所以可以考慮建立一個(gè)頻次數(shù)組 cnt[i]cnt[i] ，表示數(shù)字 ii 出現(xiàn)的次數(shù)，那么對(duì)于數(shù)字 ii 而言，它的答案：即小于它的數(shù)字出現(xiàn)個(gè)數(shù)之和，直接算需要遍歷 [0,i-1][0,i?1] 的 cntcnt 求和，仍需要線性的時(shí)間去計(jì)算，但我們注意到這個(gè)答案是一個(gè)前綴和，所以我們可以再對(duì) cntcnt 數(shù)組求前綴和。那么對(duì)于數(shù)字 ii 的答案就是 cnt[i-1]cnt[i?1] ，算答案的時(shí)間復(fù)雜度從 O(n)O(n) 降到了 O(1)O(1) 。

最后整個(gè)算法流程為：遍歷數(shù)組元素，更新 cntcnt 數(shù)組，即 cnt[nums[i]]+=1 ，然后對(duì) cntcnt 數(shù)組求前綴和，最后遍歷數(shù)組元素，對(duì)于相應(yīng)的數(shù)字 O(1)O(1) 得到答案即可。

計(jì)數(shù)排序是一種特殊的桶排序，一般適用于排序數(shù)據(jù)長(zhǎng)度n遠(yuǎ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 的計(jì)數(shù)數(shù)組
        $result = array_fill(0, $count, 0);   // 填充 0 的結(jié)果數(shù)組
        // $nums 中出現(xiàn)的值和數(shù)量對(duì)應(yīng)落到 $cnt 中
        foreach ($nums as $num) {
            $cnt[$num]++;
        }
        // $cnt 轉(zhuǎn)化成 $i 的值是 sum($cnt[0], .. $cnt[$i - 1]) 新數(shù)組，即為小于 $i 的數(shù)據(jù)數(shù)量
        foreach (range(1, 100) as $i) {
            $cnt[$i] += $cnt[$i - 1];
        }
        // 結(jié)果數(shù)組中出現(xiàn)的 索引值 替換為 計(jì)數(shù)數(shù)組中的 數(shù)量
        foreach (range(0, $count - 1) as $i) {
            if ($nums[$i]) {
                $result[$i] = $cnt[$nums[$i] - 1];
            }
        }
        return $result;
    }}

感謝各位的閱讀，以上就是“php怎么計(jì)算多少數(shù)字小于當(dāng)前數(shù)字”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)php怎么計(jì)算多少數(shù)字小于當(dāng)前數(shù)字這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

網(wǎng)站題目：php怎么計(jì)算多少數(shù)字小于當(dāng)前數(shù)字
本文來(lái)源：http://muchs.cn/article12/pisjgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營(yíng)銷型網(wǎng)站建設(shè)、定制開(kāi)發(fā)、網(wǎng)站改版、、Google、網(wǎng)站導(dǎo)航

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容