专栏首页Node.js开发算法题之优势洗牌

算法题之优势洗牌

今天解析一道名为优势洗牌的算法题目,这道题有点类似田忌赛马,来看看题目描述:

给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列,使其相对于 B 的优势最大化。

示例 1:

输入:A = [2,7,11,15], B = [1,10,4,11]
输出:[2,11,7,15]

示例2

输入:A = [12,24,8,32], B = [13,25,32,11]
输出:[24,32,8,12]

我们用示例2来说明,A、B两个数组长度一样,将A数组进行排列,让后逐项与B数组进行比较, A[i]>B[i]的一分,使分数最大化。

看起来很简单,但是该如何思考呢?从哪里下手呢?

我们可以先将A数组进行排序,从小到大进行排序,排序完成后,循环遍历B数组,用B数组中的每一项,去A数组中查找比这一项刚好大一点的数据,查找到后,将其放入到对应位置,如果查找不到从排序完成的A数组中抽出最小的放到当前位置。

计算流程图如下:我们以实例2为例进行分析。

第一步:

第二步: 遍历循环B数组中每一项,在排序完的A数组中找到比当前项大的数据。

第三步:

第四步:

第五步:

原理类似于田忌赛马,用A数组中的最小的数据,对冲B数组中的比较大的数据,剩下A数组中的数据挑选略大于B数组中的数据。代码如下:

function comp(arr1, arr2) {
  var arr = [];
  arr1.sort(function(a, b) {
    return a - b;
  });
  arr2.forEach(function(item) {
    var index = arr1.findIndex(function(_item) {
      return _item > item;
    });
    if (index > -1) {
      arr.push(arr1.splice(index, 1)[0]);
    } else {
      arr.push(arr1.splice(0, 1)[0]);
    }
  });
  return arr;
}

本文分享自微信公众号 - nodejs全栈开发(geekclass),作者:挥刀北上

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • javascript数组拍平的两种方法

    下面笔者将为大家演示一下,将一个多维数组拍平成一个一维数组的两种方法,算是抛砖引玉,大家有更好的方法可以在留言区发表。

    挥刀北上
  • 算法题之数组连续筛选处理

    大体思路就是循环遍历,每次遍历判断当前项是否与前一项差值为1,这里需要考虑若结果为1,如何处理,结果不为1如何处理。

    挥刀北上
  • 一道关于组合的js算法题目

    有一个数组,如果有3个值:[3,2,6]。交叉组合后返回:3-2,3-6,2-6,3-2-6

    挥刀北上
  • 图解Java数据结构之稀疏数组

    在编程中,算法的重要性不言而喻,没有算法的程序是没有灵魂的。可见算法的重要性。 然而,在学习算法之前我们需要掌握数据结构,数据结构是算法的基础。 我在大学的...

    wangweijun
  • javascript中Array的操作

    concat(组合数组) join(数组转字符串) pop(删除最后一个元素) shift(删除第一个元素) push(在数组尾部添加新元素) unshift(...

    Java中文社群-磊哥
  • 一起来学matlab-matlab学习笔记11 11_1 低维数组操作repmat函数,cat函数,diag函数

    本文为matlab自学笔记的一部分,之所以学习matlab是因为其真的是人工智能无论是神经网络还是智能计算中日常使用的,非常重要的软件。也许最近其带来的一...

    DrawSky
  • 【Java】基础12:什么叫数组?

    {1,2,3,4,5,6}:提前初始化数组的元素,可以有任意多个,但元素的类型要和前面定义的数据类型相匹配。

    刘小爱
  • 猿进化系列4——超速进化,一发入魂

    看完上一个章节,相信你已经掌握了程序设计的基本语句——成功的长出了猴毛了!不要小看这一点点猴毛噢,你以后的猿类生涯,这些最基础的毛毛要陪伴你渡过漫长的岁月——

    山旮旯的胖子
  • 企业面试题:js编写数组去重方法

    【友情提示:舒克老湿意在为各位准备从事前端工程师岗位的小伙伴提供思路,所有代码仅供参考,切勿背题!!理解问题以及提高自己解决问题的能力最为重要!如果你有更好的解...

    舒克
  • numpy之数组基础

    展平 ravel 只显示变为一维数组的视图 flatten将多维数组变成一维数组后保存结果

    用户7886150

扫码关注云+社区

领取腾讯云代金券