javascript - 数组，对象的一个功能实现，for循环快绕晕了，有什么好的方法

Question

Example

var wishlist = [
    {name: "Mini Puzzle", size: "small", clatters: "yes", weight: "light"},
    {name: "Toy Car", size: "medium", clatters: "a bit", weight: "medium"},
    {name: "Card Game", size: "small", clatters: "no", weight: "light"}
];

var presents = [
    {size: "medium", clatters: "a bit", weight: "medium"},
    {size: "small", clatters: "yes", weight: "light"}
];

guessGifts(wishlist, presents); // must return ["Toy Car", "Mini Puzzle"]

怎么实现guessGifts这个功能，codewars遇到的题目，自己写了一半天没写出来。
我想说明一下，wishlist.length和presents.length的个数未知,并且里面的键值对也是未知的，循环遍历的话要嵌套好几层，有没有其他更简单的办法？

Answer 1

如果是要大量处理的话，把size, clatters, weight拼成一个属性value,再做一点映射。譬如:
size: 'small' -> 0 'medium' -> 1 'large' -> 2 //and so on ...
clatters: 'no' -> 0 'a bit' -> 1 'yes' -> 2
weight: 'light' -> 0 'medium' -> 1 'heavy' -> 2 ...
那么'Card Game'对应的value就是 000 .
这样wishlist就像一个map，每一个name(key)对应一个value，然后presents里面全存的都是value，然后你就
根据这个value去找对应的key就行了，只不过这个key不一定是唯一的。
至于是要先把wishlist全部预处理还是用到了某一个name再处理这一条的内容再缓存，就看你的需求了。

Answer 2

var wishlist = [
  {name: "Mini Puzzle", size: "small", clatters: "yes", weight: "light"},
  {name: "Toy Car", size: "medium", clatters: "a bit", weight: "medium"},
  {name: "Card Game", size: "small", clatters: "no", weight: "light"}
];

var presents = [
  {size: "medium", clatters: "a bit", weight: "medium"},
  {size: "small", clatters: "yes", weight: "light"}
];

function guessGifts(wish, present){
  var dict = {};
  var ret = [];
  // normalize special key
  var normalize = function(v){
    return JSON.stringify({
      size: v.size,
      clatters: v.clatters,
      weight: v.weight
    });
  };

  wish.forEach(function(v){
    var key = normalize(v);
    dict[key] = v.name;
  });

  present.forEach(function(v){
    var key = normalize(v);
    if ( dict[key] ) {
      ret.push(dict[key]);
    }
  });

  return ret;
}

guessGifts(wishlist, presents); // must return ["Toy Car", "Mini Puzzle"]

Answer 3

给一个比较傻的方法，把属性转成string再比较 :)

var result = [];

var presentsString = [];

for (var p of presents) {
    presentsString.push(JSON.stringify(p))
}

for (var v of wishlist) {
    var name = v.name;
    delete v.name;
    for (var pp of presentsString) {
        if (JSON.stringify(v) === pp) result.push(name);
    }
}

console.log(result);

Answer 4

我也试个，尽量用一个for:

function guessGifts( wishlist, presents){

     var gifts  =  newWishList = [];

     for( var key in wishlist ){
         
        var name = wishlist[key].name;
         delete wishlist[key].name;
         
        presents.filter(function( gift ){        
        
              if(JSON.stringify( gift ) === JSON.stringify( wishlist[key] )){
                 gifts.push( name );
             }
        });
     }
     
     return gifts;
}

var guessGift   = guessGifts( wishlist, presents );

console.log( guessGift ); // ["Toy Car", "Mini Puzzle"]

Answer 5

楼主，这是要根据关键字weight来关键字来关联两组数据？？？

Answer 6

O(n)搞之，先遍历presents，把要求的东西存到一个标记数组里面，key可以设置为（size: "medium", clatters: "a bit", weight: "medium"，key怎么存自己搞定），value为1，保证唯一，然后扫一下wishlist数组，看生成的key是否在标记数组里面，如果在则输出。尽提供思路。

Answer 7

var guessGifts = function (wishlist, presents) {
  'use strict'
  return presents.map(function(giftInfo) {
    for(var i = 0; i < wishlist.length; i++) {
      if(fit(wishlist[i], giftInfo)) {
        return wishlist[i].name;
      }
    }
  });
}

function fit(gift, giftInfo) {
  'use strict'
  for (var p in giftInfo) {
    if(gift[p] !== giftInfo[p])
    return false;
  }
  return true;
}

简单实现 时间复杂度o(n*m)。用到了ES5的数组map方法。在nodejs 5.3下测试通过。考虑到了不固定属性名。

Answer 8

下面时间复杂度为n²

function guessGifts (arr1, arr2) {
    // 首先遍历数组2,找出条件
    var keys = arr2.map(function (ele) {
        var arr = [];
        var keys = Object.keys(ele);
        for (var i = 0, len = keys.length; i < len; i++) {
            arr[i] = ele[keys[i]];
        }
        return arr;
    });
    // 根据条件数组筛选
    var result = arr1.filter(function (ele) {
        for (var i = 0, len = keys.length; i < len; i++) {
            if (keys[i].indexOf(ele.clatters) !== -1 && 
                  keys[i].indexOf(ele.size) !== -1 && 
                     keys[i].indexOf(ele.weight) !== -1) {
                return true;
            }
        }
        return false;
    });
    // 取出筛选后数组的name
    result = result.map(function (ele) {
        return ele.name;
    });
    return result;
}

Answer 9

时间复杂度O(n+m)

function guessGifts(wishlist, presents) {
    let re = [], wt = [],
        size = {small: 1, medium: 2, large: 3 },
        clatters = {no: 10, 'a bit': 20, yes: 30 },
        weight = {light: 100, medium: 200, heavy: 300 }
    for(item of wishlist) {
        let w = size[item.size] + clatters[item.clatters] + weight[item.weight]
        if(!wt[w]) {
            wt[w] = []
        }
        wt[w].push(item.name)
    }
    for(item of presents) {
        let w = size[item.size] + clatters[item.clatters] + weight[item.weight]
        if(wt[w]) {
            re = [...re, ...wt[w]]
            delete wt[w]
        }
    }
    return re
}

过了之后看了一下其他人的答案。。。虽然用全了特性，但是效率低，但是毕竟是javascript，谁在意性能呢;）

Answer 10

一个比较懒的写法

function guessGifts(type1,type2){
   var lastArr=[];
   type1.forEach(function(item){     
        type2.forEach(function(subitem,index){
            var k=0;
            for(var i in subitem){
                k++;
                if(!item.hasOwnProperty(i) || item[i]!==subitem[i]){ break;}
                if(k===type2.length) lastArr.push(item["name"]); 
            }
        });     
   });
   return lastArr;
}