. 어레이 패치 중

330. 어레이 패치

하드

정렬된 정수 배열 nums와 정수 n이 주어지면 [1, n] 범위의 모든 숫자가 배열의 일부 요소의 합으로 구성될 수 있도록 배열에 요소를 추가/패치합니다.

필요한 최소 패치 수를 반환합니다.

예 1:

• 입력: 숫자 = [1,3], n = 6
• 출력: 1
• 설명:
  • 숫자의 조합은 [1], [3], [1,3]이며 가능한 합은 1, 3, 4입니다.
  • 이제 숫자에 2를 추가/패치하면 조합은 [1], [2], [3], [1,3], [2,3], [1,2,3]이 됩니다.
  • 가능한 합은 1, 2, 3, 4, 5, 6이며 이제 범위는 [1, 6]입니다.
  • 그래서 패치는 1개만 필요합니다.

예 2:

• 입력: 숫자 = [1,5,10], n = 20
• 출력: 2
• 설명: 두 개의 패치는 [2, 4]일 수 있습니다.

예 3:

• 입력: 숫자 = [1,2,2], n = 5
• 출력: 0

제약조건:

• 1 <= nums.length <= 1000
• 1 <= 숫자[i] <= 10⁴
• nums는 오름차순으로 정렬됩니다.
• 1 31 - 1

해결책:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $n
     * @return Integer
     */
    function minPatches($nums, $n) {
        $ans = 0;
        $i = 0;
        $miss = 1;
         while ($miss <= $n) {
            if ($i < count($nums) && $nums[$i] <= $miss) {
                $miss += $nums[$i++];
            } else {
                $miss += $miss;
                ++$ans;
            }
        }
        return $ans;
    }
}

연락처 링크

• 링크드인
• 깃허브

위 내용은 . 어레이 패치 중의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!