[LeetCode 34]PHPは配列の中で元素の第1と最後の位置を探すことを求めます

原文リンク:のブログ
ソート配列で要素の最初の位置と最後の位置を検索
昇順に配列された整数配列numsと、目標値targetが与えられる.配列内の所定のターゲット値の開始位置と終了位置を特定します.
配列にターゲット値targetが存在しない場合は、[-1, -1]を返します.
ステップ:

時間複雑度O(log n)のアルゴリズムを設計して実現できますか?

 
例1:

  ：nums = [5,7,7,8,8,10], target = 8
  ：[3,4]

例2:

  ：nums = [5,7,7,8,8,10], target = 6
  ：[-1,-1]

例3:

  ：nums = [], target = 0
  ：[-1,-1]

ヒント:

0 <= nums.length <= 105

-109 <= nums[i] <= 109

numsは非減算配列

である

-109 <= target <= 109

出典:LeetCode(LeetCode)リンク:https://leetcode-cn.com/probl...著作権はバックルネットワークの所有に帰属する.商業転載は公式の授権に連絡し、非商業転載は出典を明記してください.
問題を解く考え方1
暴力捜査と特殊な結果の処理

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function searchRange($nums, $target) {
        //       

        $result = [-1, -1];

        if (empty($nums)) {
            return $result;
        }

        //    +      $result

        $i = 0;
        foreach ($nums as $key => $num) {
            if ($num == $target) {
                if ($i == 0) {
                    $result[0] = $key;
                } else {
                    $result[1] = $key;
                }
                $i++;
            }
        }

        //           

        if ($result[0] !== -1 && $result[1] == -1) {
            return [$result[0], $result[0]];
        }

        return $result;
    }
}

問題を解く考え方2
二分法の考え方を利用して、まず二分法を利用してtargetに合致する値を見つけて、更にそれぞれ二分法でtargetの開始の位置と終了の位置を求めます.

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function searchRange($nums, $target) {
        $result = [-1, -1];
        if (empty($nums)) {
            return $result;
        }

        $left = 0;
        $count = count($nums);
        $right = $count - 1;
        while ($left <= $right) {
            $mid = round($left + ($right - $left) / 2);
            if ($nums[$mid] == $target) {
                $left = $mid;
                $right = $mid;
                //    $nums[$left - 1] == $nums[$left],           

                while ($left > 0 && $nums[$left - 1] === $nums[$left]) {
                    --$left;
                }

                //    $nums[$right + 1] == $nums[$right],           

                while ($right < $count - 1 && $nums[$right] === $nums[$right + 1]) {
                    ++$right;
                }

                $result[0] = $left;
                $result[1] = $right;
                break;
            } else if ($nums[$mid] > $target) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }

        return $result;
    }
}

参照リンク:

極客時間アルゴリズム面接通関40講

最後のチャペル阿里雲全シリーズ製品/メールパック特恵中小企業上雲ベスト選択阿里雲内部クーポン購入