数组，对象的一个功能实现，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;
}

Answer 11

wishlist.length和presents.length的个数未知,并且里面的键值对也是未知的

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(wishlist,presents){
    var someWish=wishlist[0];
    var keys=[];
    for(var prop in someWish){
        if(someWish.hasOwnProperty(prop)){
            keys.push(prop);
        }
    }

    var somePresent;
    var matchScores={};
    for(var i= 0,presentLengt=presents.length;i<presentLengt;i++){
        somePresent=presents[i];
        keys.forEach(function(key){
            if(somePresent[key]){
                wishlist.forEach(function(item,index){
                    if(item[key]===somePresent[key]){
                        //console.log('match value:%s presend:%d wishlist:%d',somePresent[key],i,index);
                        if(!matchScores[i+'_'+index]){
                            matchScores[i+'_'+index]={
                                score:0,
                                wishIndex:index
                            };
                        }
                        matchScores[i+'_'+index].score=matchScores[i+'_'+index].score+1;
                    }
                });
            }
        });
    }

    var resut=[];
    for(prop in matchScores){
        if(matchScores.hasOwnProperty(prop)){
            resut.push(matchScores[prop]);
        }
    }

    resut.sort(function(itemA,itemB){
        return itemB.score-itemA.score;
    });

    console.log(resut.slice(0,presents.length).map(function(item){
        if(wishlist[item.wishIndex].name){
            return wishlist[item.wishIndex].name;
        }else{
            return wishlist[item.wishIndex];
        }

    }));

}

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

Answer 12

写完了才发现和要求不是很一致，囧
题目以presents的顺序返回名称，现在这个以wishlist的顺序返回
有空再改吧。

'use strict';
describe('guess gift test', function(){
    function guessGifts(wishlist, presents) {
        return wishlist.filter(anyone_matcher(presents)).map(giftName);
    }
    function anyone_matcher(presents) {
        return function (gift) {
            return presents.some(matcher(gift));
        }
    }

    function matcher(gift) {
        return function (present) {
            for (var field in present) {
                if (gift[field] !== present[field]) return false;
            }
            return true;
        }
    }
    function giftName(gift) { return gift.name; }

    // tests start here
    it("should return empty array if none wish or presents", function() {
        expect(guessGifts([], [])).toEqual([]);
    });

    it("should return matched 1 filed gift with 1 criteria", function() {
        expect(guessGifts([{name:'g1'}], [{name:'g1'}])).toEqual(['g1']);
        expect(guessGifts([{name:'g1'},{name:'g2'}], [{name:'g1'}])).toEqual(['g1']);
        expect(guessGifts([{name1:'g1'},{name1:'g2'}], [{name1:'g2'}])).toEqual([undefined]);
    });

    it("should return matched gifts with criterias", function() {
        var wishlist = [
            {name:'g1', size: 'small', wight: 'light'},
            {name:'g2', size: 'medium', wight: 'light'}
        ];
        var presents = [
            {size: 'medium', wight: 'light'}
        ];
        expect(guessGifts(wishlist, presents)).toEqual(['g2']);
    });

    it("should return matched gifts with more than 1 criterias", function() {
        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'}
        ];

        expect(guessGifts(wishlist, presents)).toEqual(['Mini Puzzle', 'Toy Car']);
    });
});

Answer 13

最终版本

var guessGifts = function(wishlist, presents) {
  
    var result = [];
  
    _.each(presents, function(item) {
        result.push(_.pluck(_.filter(wishlist, item), 'name'));
    });


    return _.flatten(result);

};

下面的内容为前面的版本

导入lodash插件，然后就简单了

var result = _.filter(wishlist, function(item) {
    return _.some(presents, function(v) {
        return v.size == item.size && v.weight == item.weight && v.clatters == item.clatters;
    });
});

console.log(result);

简单版本

var result =[];
_.each(presents,function(item){
  result.push(_.filter(wishlist,item));
});

console.log(result);

Answer 14

提问者这是要问什么？

Answer 15

从2个数组的关系以及返回结果来看，应该就是presents中的属性与wishlist中的后三个属性相同，然后取wishlist中的name组成数组作为返回结果。因此我想到的解决方案如下：

1. 转换wishlist的结构如下

var wishlistC = [
    {
        name: "Mini Puzzle", 
        info: {
            ...
        }
     },
    ...
];

1. 比较wishlistC[i].info与presents[n]，如果他们相等，则取到wishlistC[i].name，然后组成数组返回。

思路很简单，这里有一个比较麻烦的地方就是如何比较2个对象相同，因此这边自己定义了一个方法用来比较

这里实现的这个方法比较健全，如果仅仅只是为了满足题主的问题，只需要遍历一下presents中的属性，能够在wishlist中找到并相等即可。有点类似楼上某位同学的fit方法

// 比较2个内容是否相等，他们可以是数组，对象，字符串，数字等
function equal(objectA, objectB) {
    // 如果类型不同，不等
    if (typeof objectA != typeof objectB) {
        return false;
    }

    // array
    if (objectA instanceof Array && objectB instanceof Array) {
        if (objectA.length != objectB.length) {
            return false;
        };

        var tagArray = true;

        for(var i=0; i<objectA.length; i++) {
            if (typeof objectA[i] != typeof objectB[i]) {
                tagArray = false;
                return tagArray;
            };
            if (typeof objectA[i] == 'number' || typeof objectA[i] == 'string') {
                if (objectA[i] != objectB[i]) {
                    tagArray = false;
                    return tagArray;
                };
            } else {
                tagArray = arguments.callee(objectA[i], objectB[i]);
            }

            return tagArray;
        }
    }

    // object
    if (objectA instanceof Object && objectB instanceof Object) {
        var result = true,
            lengthA = 0,
            lengthB = 0;

        for(var item in objectA) {
            if (typeof objectA[item] == 'number' || typeof objectA == 'string') {
                if (objectA[item] != objectB[item]) {
                    result = false;
                    return result;
                };
            } else {
                if (!arguments.callee(objectA[item], objectB[item])) {
                    result = false;
                    return result;
                };
            }

            lengthA ++;
        }

        for(var item in objectB) {
            lengthB ++;
        }

        if (lengthA != lengthB) {
            result = false;
        };
        return result;
    };

    return objectA == objectB;
}

那么接下来就比较简单了

function guessGifts(wishlist, presents) {
    var wishlistC = [];

    for(var i = 0; i<wishlist.length; i++) {
        var demo = {
            name: wishlist[i].name,
            info: {}
        };
        for(var n in wishlist[i]) {
            if (n != 'name') {
                demo.info[n] = wishlist[i][n];
            };
        }

        wishlistC.push(demo);
    }
    console.log(wishlistC);

    var result = [];

    for(var i in wishlistC) {
        for(var m in presents) {
            if (equal(wishlistC[i].info, presents[m])) {
                result.push(wishlistC[i].name);
            };
        }
    }

    return result;

};

看了楼上的回答，这里解释一下为什么一定要比较对象相等，而不是为了降低时间复杂度比较拼接的字符串或者其他形式。因为对象中，属性的位置是没有顺序问题的，直接比较对象会更加灵活而满足需求。

因此总的来说，无论怎么转换，比较对象内容相等在我看来是不可避免的一步。

Answer 16

document.addEventListener('DOMContentLoaded', function(){
  var ret = document.getElementById('ret');
  guesss(ret, wishlist, presents);
});
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"}
],
presents = [
  {size: "medium", clatters: "a bit", weight: "medium"},
  {size: "small", clatters: "yes", weight: "light"}
],
guesss = function(elem, list, require){
  var str = '无',
      list = list || [],
      require = require || [],
      serialKey = function(item){
        return [item.size, item.clatters, item.weight].join(', ');
      };
  if(elem && require.length > 0 && list.length > 0){
    var listMap = {};
    list.forEach(function(item){
      var key = serialKey(item),
          val = item.name;
      listMap[key.toLowerCase()] = val;
    });
    require.forEach(function(item){
      var key = serialKey(item),
          val = listMap[key.toLowerCase()];
      if(val){
        if(str === '无'){
          str = '';
        }
        str += '<p>Gift is: '+ val +'<br> Key is: '+ key +'</p>';
      }
    });
  }
  elem.innerHTML = str;
};

http://codepen.io/interjc/pen/ZQrNRz?editors=0010