题目描述

小扣在秋日市集选择了一家早餐摊位,一维整型数组 staple 中记录了每种主食的价格,一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料,且花费不超过 x 元。请返回小扣共有多少种购买方案。注意：答案需要以 1e9 + 7 (1000000007) 为底取模,如：计算初始结果为：1000000008,请返回 1

题目分析

购买方案
答案取模

参数说明

/**
 * @param {number[]} staple
 * @param {number[]} drinks
 * @param {number} x
 * @return {number}
 */

题解及实现

1.双指针

很明显,双层暴力即使做剪纸也是超时的,所以决定先将两个数组进行排序再用双指针从头尾分别遍历

var breakfastNumber = function (staple, drinks, x) {
  staple.sort((a, b) => a - b);
  drinks.sort((a, b) => a - b);
  let cnt = 0;
  let i = 0;
  let j = drinks.length - 1;
  while (i < staple.length && j >= 0) {
    if (staple[i] + drinks[j] <= x) {
      cnt = (cnt % 1000000007) + j + 1; //一个符合,那小于这个价格的饮料都是符合的
      i++;
    } else j--;
  }
  return cnt;
};

时间复杂度:与内部算法实现有关

资源使用情况
- 执行用时：532 ms, 在所有 JavaScript 提交中击败了 32.67%的用户
- 内存消耗：62.5 MB, 在所有 JavaScript 提交中击败了 44.68%的用户
  问题:排序耗时

2.二分查找

将 drinks 数组进行排序,将 x-staple 作为买食物剩下的钱在 drinks 数组中做二分查找,返回能买的份数

var breakfastNumber = function (staple, drinks, x) {
  drinks.sort((a, b) => a - b); //排序用于二分查找
  let cnt = 0;
  for (food of staple) {
    y = x - food;
    if (y > 0) cnt = (cnt % 1000000007) + bs(drinks, y) + 1;
  }
  return cnt;
};

function bs(arr, x) {
  let j = 0;
  let i = arr.length - 1;
  let middle;
  while (j <= i) {
    middle = Math.floor((i + j) / 2);
    if (arr[middle] === x) break;
    if (arr[middle] > x) i = middle - 1;
    if (arr[middle] < x) j = middle + 1;
  }
  //找到最右边的那份
  if (arr[middle] === x) {
    while (middle + 1 < arr.length) {
      if (arr[middle + 1] === x) middle++;
      else return middle;
    }
    return middle;
  } else return i;
}

时间复杂度:O((m+n)log(n),n 为 drinks 数组长度)

资源使用情况
- 执行用时：472 ms, 在所有 JavaScript 提交中击败了 72.91%的用户
- 内存消耗：58.9 MB, 在所有 JavaScript 提交中击败了 93.44%的用户

同思路优化版,将短的数组进行排序

var breakfastNumber = function (staple, drinks, x) {
  let sortArr;
  let ergArr;
  if (drinks.length < staple.length) {
    sortArr = drinks.sort((a, b) => a - b);
    ergArr = staple;
  } else {
    sortArr = staple.sort((a, b) => a - b);
    ergArr = drinks;
  }
  let cnt = 0;
  for (item of ergArr) {
    y = x - item;
    if (y > 0) cnt = (cnt % 1000000007) + bs(sortArr, y) + 1;
  }
  return cnt;
};

function bs(arr, x) {
  let j = 0;
  let i = arr.length - 1;
  let middle;
  while (j <= i) {
    middle = Math.floor((i + j) / 2);
    if (arr[middle] === x) break;
    if (arr[middle] > x) i = middle - 1;
    if (arr[middle] < x) j = middle + 1;
  }
  if (arr[middle] === x) {
    while (middle + 1 < arr.length) {
      if (arr[middle + 1] === x) middle++;
      else return middle;
    }
    return middle;
  } else return i;
}

资源使用情况
- 执行用时：372 ms, 在所有 JavaScript 提交中击败了75.70%的用户
- 内存消耗：58.3 MB, 在所有 JavaScript 提交中击败了94.26%的用户

2020-10-27 早餐组合