3-25 1300. 转变数组后最接近目标值的数组和

Date：2022-03-25 07:17:05

标签：

二分查找算法
前缀和

前置问题：

704. 二分查找 ( 简单😄 )

题目：1300. 转变数组后最接近目标值的数组和 ( 中等😕 )

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

示例

示例1：

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

示例2：

输入：arr = [2,3,5], target = 10
输出：5

示例3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

分析

重点：

prefix[i]前缀和包不包含nums[i]都可以，只要不计算重复

难点：

二分查找法中的边界问题

题解

二分查找

function findBestValue(arr: number[], target: number): number {
  arr.sort((a, b) => a - b)

  // console.log('[arr]:', arr)

  const len = arr.length
  const prefix: number[] = new Array(len + 1).fill(0)

  for (let i = 1; i <= len; ++i) {
    prefix[i] = prefix[i - 1] + arr[i - 1]
  }

  // console.log('[prefix]:', prefix)

  let ans = 0,
      diff = target,
      max = arr[len - 1]

  for (let i = 1; i <= max; ++i) {
    let index = binarySearch(arr, i)

    // console.log('[index111]:', index)

    if (index < 0) {
      index = -index - 1
    }

    const sum = prefix[index] + (len - index) * i
    const curr = Math.abs(sum - target)

    // console.log('[diff]:', diff, prefix[index], index, i, sum, curr)

    if (curr < diff) {
      ans = i
      diff = curr
    }
  }

  return ans

  function binarySearch(nums: number[], target: number): number {
    if (nums.length <= 0 || target < nums[0] || target > nums[nums.length - 1]) {
      return -1
    }

    let left = 0,
        right = nums.length - 1

    while (left <= right) {
      const mid = Math.floor((right - left) / 2) + left

      const num = nums[mid]

      if (target == num) {
        return mid
      } else if (target > num) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }

    return -(left + 1)
  }
}

使用

function main() {
  // const arr = [4, 9, 3],
  //   target = 10
  // const arr = [2, 3, 5],
  //   target = 10
  // const arr = [60864, 25176, 27249, 21296, 20204],
  // target = 56803

  // [ 20204, 21296, 25176, 27249, 60864 ]

  console.log('[]:', findBestValue(arr, target))
}

main()

export {}

扩展1：704. 二分查找

题目：704. 二分查找 ( 简单😄 )

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例