PHPで現在の数値より小さい数値の数を計算する方法

配列 nums を与えます。各要素 nums[i] について、配列内のそれより小さいすべての数値の数を数えてください。どうすればよいですか?今回は、現在の数字より何個小さいかを計算する方法を編集者が紹介しますので、必要な場合は参考にしてください。

配列 nums が与えられた場合、各要素 nums[i] について、配列内のそれより小さいすべての数値の数を数えてください。

言い換えると、 nums[i] ごとに、 j != i および nums[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 <= 500

• ##0 <= nums[i] < ; = 100

解決策のアイデア 1

配列内の各数値を列挙し、配列を走査して、現在の数値より小さい数値がいくつあるかを数えます。 Just

コード

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 ] であることに注意してください。したがって、数値 ii が出現する回数を表す頻度配列 cnt[i]cnt[i] を確立することを検討できます。次に、数値 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で現在の数値より小さい数値の数を計算する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。