检查一个元素是否只存在于一个数组中的更好方法

29

我需要帮助创建一个函数,以返回仅出现在3个数组中的其中一个中的元素,例如

let arr1 = ['a', 'b', 'c', 'a', 'b']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']

在上述三个数组中,'d'和'f'仅存在于其中一个数组(arr2和arr3)中,我需要返回它们。
['d','f']

数组的大小可能不同,返回的元素不能重复。

我尝试寻找更好的解决方案,但失败了,最终采用了暴力方法,循环遍历每个数组并检查元素是否存在于其他两个数组中。显然,这种方法非常慢且难以阅读。

function elementsInOnlyOneArr(a1, a2, a3) {

  let myArr = [];

  for(let el of a1){
    if(a2.includes(el) == false && a3.includes(el) == false && myArr.includes(el) == false){
      myArr.push(el);
    }
  }

  for(let el of a2){
    if(a1.includes(el) == false && a3.includes(el) == false && myArr.includes(el) == false){
      myArr.push(el);
    }
  }

  for(let el of a3){
    if(a2.includes(el) == false && a1.includes(el) == false && myArr.includes(el) == false){
      myArr.push(el);
    }
  }


  return myArr;
}

数组中的元素是否总是字母或字符串? - codingStarter
3
这里有多少个元素? - Chris Schaller
3
我认为标题应该说“仅存在于一个数组中”。 - Wyck
嗨,它们将是字符串。 - kilex
10个回答

25

假设数组数量小于32个,您可以使用位图高效地完成此操作。基本上,建立一个索引key -> number,其中如果键在第N个数组中,则数字设置了第N位。最后返回只有单个位设置(=是2的幂)的数字对应的键:

function difference(...arrays) {
    let items = {}

    for (let [n, a] of arrays.entries())
        for (let x of a) {
            items[x] = (items[x] ?? 0) | (1 << n)
        }

    return Object.keys(items).filter(x => 
        Number.isInteger(Math.log2(items[x])))
}


let arr1 = ['a', 'b', 'c', 'a', 'b', 'z', 'z', 'z']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']

console.log(difference(arr1, arr2, arr3))

(如评论中所述,x & (x-1) === 0更符合惯用法,可用于检查x是否为2的幂。请参见公式x & (x - 1)是如何工作的?进行解释。)
这里有一种更通用的方法,不限制数组数量,也不要求键必须是字符串:

function difference(...arrays) {
  let items = new Map

  for (let [n, a] of arrays.entries())
    for (let x of a) {
      if (!items.has(x))
        items.set(x, new Set)
      items.get(x).add(n)
    }

  let result = []

  for (let [x, ns] of items)
    if (ns.size === 1)
      result.push(x)

  return result
}

let arr1 = ['a', 'b', 'c', 'a', 'b', 'z', 'z', 'z']
let arr2 = ['a', 'd', 'b', 'c']
let arr3 = ['f', 'c', 'a']

console.log(difference(arr1, arr2, arr3))


6
"(x & (x-1)) == 0" 可以测试2的幂,而不使用log或isInteger。 - ralphmerridew
7
为什么要这样实现,而不是将键映射到计数器并返回计数为1的键?这个答案似乎过于复杂。 - Overv
@Overv:编辑了示例以使观点更加清晰。 - gog
@ScottSauyet:看起来这些例子已经可以正常工作了。 - gog
抱歉,我之前的评论有些混淆。我已经像其他答案一样将输入元素包装在一个数组中。这很好地解决了我的问题:http://link.fourwindssoft.com/74。这里有很多答案都做错了。这是一个非常有趣的方法! - Scott Sauyet

10

编辑:误解了问题,它不是求交集,而是提取个别数组之间唯一的值(例如不是交集),为此可能会起作用:

let arr1 = ['a', 'b', 'c', 'a', 'b'];
let arr2 = ['a', 'd', 'b', 'c'];
let arr3 = ['f', 'c', 'a'];

const thereCanOnlyBeOne = function(...arrs) {
    return Array.from(
        arrs.reduce((map, arr) => {
            new Set(arr).forEach((v) => map.set(v, map.has(v) ? map.get(v)+1 : 1));
            return map;
        }, new Map())
    )
    .filter(([value, count]) => count === 1)
    .map(([value, count]) => value);
};

console.log(thereCanOnlyBeOne(arr1, arr2, arr3));

我认为@gog的答案更加复杂,可能会更快,但我有些难以理解(叫我蠢,我接受 =D,编辑:不得不进行一些研究,阅读/学习一些关于位集 在这里 在这里), 所以这是使用Map和数组方法略微复杂的方式的分解:

  1. 将要分析的所有数组传递到函数中,顺序无关紧要
  2. 循环(我选择reduce,但任何循环结构都可以)遍历所有输入数组及其值,在Map中计算出现次数,最后Map将如下所示:
0: {"a" => 4}
1: {"b" => 3}
2: {"c" => 3}
3: {"d" => 1}
4: {"f" => 1}
  • 完成后,我们通过Array.from()将Map转换回数组,创建一个元组数组:
  • [
       ["a", 4],
       ["b", 3],
       ["c", 3],
       ["d", 1],
       ["f", 1],
    ]
    

    将现在形如 [<value>, <count>] 的元组数组过滤,只保留确切出现一次的值,得到:
    [
       ["d", 1],
       ["f", 1],
    ]
    
    1. 对筛选后的数组进行映射,将其“简化”为一维数组,并返回结果:
    ["d", "f"]
    

    警告:在内部,此代码会执行大量循环操作,因此也可以称之为暴力循环,尽管由于“性感”的ES6数组语法糖而看起来“更短”。

    为了完整起见,稍作修改,因为可以通过迭代计数器Map一旦完成并简单地删除不具有值1的Map条目来省略Array.filter()步骤(尽管似乎更快)。

    let arr1 = ['a', 'b', 'c', 'a', 'b'];
    let arr2 = ['a', 'd', 'b', 'c'];
    let arr3 = ['f', 'c', 'a'];
    
    const thereCanOnlyBeOne = function(...arrs) {
        let result;
        
        arrs
        .reduce((map, arr) => {
            new Set(arr).forEach((v) => map.set(v, map.has(v) ? map.get(v)+1 : 1));
            
            return map;
        }, new Map())
        // the result of .reduce will be a Map!
        .forEach((value, key, map) => { value !== 1 && map.delete(key); result = map; });
        
        return Array.from(result).map(([value, count]) => value);
    };
    
    console.log(thereCanOnlyBeOne(arr1, arr2, arr3));

    更新:正如@Nick Parsons所指出的,代码的早期版本将不会输出仅存在于一个数组中但多次出现的元素。

    如果一个数组包含相同的值,并且该元素不存在于任何其他数组中,则将产生错误的输出。例如,如果从arr2中删除b,则只有arr1中有b,而其他数组则没有,因此应在最终结果中包含b。

    这可以通过将被检查的数组转换为 Set() 来轻松解决(从而将数组的值减少到“唯一”值)。

    如果有人(除了我以外)想知道,这里是gog选项和我的基准测试,他的位集方法显然是最快的,因此,如果您正在比较小于32个数组,那么这是迄今为止最有效的解决方案:https://jsben.ch/YkKSu

    如果有人喜欢gog的bitset实现的ES6版本(由@ralphmerridew提出的改进),这里是:

    let arr1 = ['a', 'b', 'c', 'a', 'b'];
    let arr2 = ['a', 'd', 'b', 'c'];
    let arr3 = ['f', 'c', 'a'];
    
    function onlyone(...arrays) {
        return Object.entries(
            arrays.reduce((map, arr, n) => {
                arr.forEach((v) => map[v] = (map[v] ?? 0) | (1 << n));
                return map;
            }, {})
        )
        .filter(([value, bitmap]) => (bitmap & (bitmap-1)) == 0)
        .map(([value, bitmap]) => value);
    };
    
    console.log(onlyone(arr1, arr2, arr3));

    已更新基准测试,有趣的是(或出乎意料的是),这个看起来“较慢”的ES6实现在chrome和firefox中多次击败了gog的for循环实现,我自己都不敢相信,以为这些语法糖方法与for循环相比会稍微拖慢速度,好吧...知道就好了 =)

    我还尝试使用BigInt()实现位集方法,以消除它只能处理32个数组的问题(取决于引擎,使用BigInt应该可以处理100万到10亿个数组),不幸的是,这似乎使它成为所有解决方案中最慢的一个(基准测试已更新):

    let arr1 = ['a', 'b', 'c', 'a', 'b'];
    let arr2 = ['a', 'd', 'b', 'c'];
    let arr3 = ['f', 'c', 'a'];
    
    function onlyoneBigInt(...arrays) {
        return Object.entries(
            arrays.reduce((map, arr, n) => {
                arr.forEach((v) => map[v] = (map[v] ?? 0n) | (1n << BigInt(n)));
                return map;
            }, {})
        )
        .filter(([value, bitmap]) => (bitmap & (bitmap-1n)) == 0)
        .map(([value, bitmap]) => value);
    };
    
    console.log(onlyoneBigInt(arr1, arr2, arr3));

    也许有人看到了可以改进使其更快的东西?


    嗯,我已经仔细阅读了 OP 的帖子十次,现在我不确定自己是否理解正确了 =) …也许这根本不是一个交集… - exside
    是的,我认为不是这样的。根据他们所说的和提供的代码,他们想要保留仅出现在一个数组中的元素。如果在该数组中重复出现,则仍应保留,但在输出中只应出现一次。 - Nick Parsons
    2
    最好使用与问题相同的输入来回答。苹果:苹果。 - Tibrogargan
    是的,你可能是对的!10秒钟内完成! - exside
    2
    我会研究一下,谢谢你提醒!这比我想象的要棘手 =) - exside
    显示剩余8条评论

    6

    这实际上只是集合操作。下面的single方法查找测试数组中未出现在集合中的其他数组中的任何条目。故意实现此功能,以便您可以测试单个数组,因为问题中不清楚您是否需要返回字母还是数组。

    let arr1 = ['a', 'b', 'c', 'a', 'b']
    let arr2 = ['a', 'd', 'b', 'c']
    let arr3 = ['f', 'c', 'a']
    
    // The set of arrays
    let arrays = [ arr1, arr2, arr3 ]
    
    // Finds any entries in the test array that doesn't appear in the arrays that aren't the test arrays
    let singles = (test) => {
      // others is the Set of all value in the other arrays
      others = arrays.reduce( ( accum, elem ) => {
        if (elem != test) { elem.forEach(accum.add, accum) }
        return accum
      }, new Set())
      // find anything in the test array that the others do not have
      return [...new Set(test.filter( value => ! others.has(value) ))]
    }
    
    // collect results from testing all arrays
    result = []
    for(const array of arrays) { result.push(...singles(array))
    }
    console.log(result)

    借鉴@gog的优秀答案中的参数构造,您还可以定义它以便接受一个测试数组和一组任意的数组进行测试:
        let singles = (test, ...arrays) => {
          // others is the Set of all value in the other arrays
          others = arrays.reduce( ( accum, elem ) => {
            if (elem != test) { elem.forEach(accum.add, accum) }
            return accum
          }, new Set())
          // find anything in the test array that the others do not have
          return [...new Set(test.filter( value => ! others.has(value) ))]
        }
    
        console.log(singles(arr2, arr1, arr2, arr3))
    

    这里的优点是,它可以适用于任意数量的数组,而gog的答案可能更适合少于32个数组的集合(或者在技术上,如果你愿意使用BigInt进行扩展,那么任何数量都可以,但这可能会失去一些速度)


    如果在 arr3 的末尾添加 'f',结果将是 ['d', 'f', 'f'],我非常确定这不是期望的结果。 - Scott Sauyet
    1
    @ScottSauyet 发现得好,已修复 - 但现在趋向于“难以阅读”,这与要求相反。 - Tibrogargan

    5
    一个相当简单的方法:

    const inOnlyOne = (
      xss, 
      keys = [... new Set (xss .flat ())], 
      uniques = xss .map (xs => new Set (xs))
    ) => keys .filter (k => uniques .filter (f => f .has (k)) .length == 1)
    
    console .log (inOnlyOne ([['a', 'b', 'c', 'a', 'b'], ['a', 'd', 'b', 'c'], ['f', 'c', 'a']]))

    我们通过将数组扁平化并将其转换为 Set,然后再转换回数组的方式来查找唯一键列表,将数组转换为集合,然后过滤键以仅查找包含该键的集合数量恰好为一个的键。

    这里有一点低效率,因为我们在检查数字是否存在于集合中时需要检查所有集合。如果修改代码只检查第二个集合,那么这很容易实现,但代码会更复杂。如果我发现这个简单版本对我的需求不够高效,我才会费心去做这件事。

    这种方法的一个优点是它适用于除字符串和数字之外的其他数据类型:

    const a = {a: 1}, b = {b: 3}, c = {c: 3}, d = {d: 4}, e = {e: 5}, f = {f: 6}
    
    inOnlyOne ([[a, b, c, a, b], [a, d, b, c], [f, c, a]])
    
    //=> [{d: 4}, {f: 6}]
    

    当然,这只有在您的项目是共享引用时才有帮助。如果您想使用值相等而不是引用相等,那么它将变得更加复杂。

    如果我们想要单独传递数组,而不是将它们包装在一个公共数组中,那么这个变体应该可以工作:

    const inOnlyOne = (...xss) => ((
      keys = [... new Set (xss .flat ())], 
      uniques = xss .map (xs => new Set (xs))
    ) => keys .filter (k => uniques .filter (f => f .has (k)) .length == 1)
    ) ()
    

    1
    我只是好奇:是哪种语言影响了你的代码风格,让你在方法名前面加一个空格?而且你在参数列表中进行"计算"的做法呢? - Niccolo M.
    1
    间距仅是一种为了突出方法本身而添加的方式。虽然有点古怪,但我发现它更易读。没有任何语言影响它。参数是从更多的FP语言中真正的let绑定的贫民版。它使我能够使用表达式而不是语句进行更多的编程,并从代码中删除了一些时间和顺序的概念。 - Scott Sauyet

    4

    这是一个类似于您自己的暴力迭代器,但通过从数组中删除项目来减少重新进入的次数:

    function elementsInOnlyOneArr(...arrays) {
    
      // de-dup and sort so we process the longest array first
      let sortedArrays = arrays.map(ar => [...new Set(ar)]).sort((a,b) => b.length - a.length);
      
      for (let ai1 = 0 ; ai1 < sortedArrays.length; ai1 ++) {
        for(let i = sortedArrays[ai1].length - 1; i >= 0; i --){
          let exists = false;
          let val = sortedArrays[ai1][i];   
          for(let ai2 = ai1 + 1 ; ai2 < sortedArrays.length ; ai2 ++) {
            let foundIndex = sortedArrays[ai2].indexOf(val);
            if (foundIndex >= 0) {
              exists = true;
              sortedArrays[ai2].splice(foundIndex,1);
              // do not break, check for match in the other arrays
            }
          }
          // if there was a match in any of the other arrays, remove it from the first one too!
          if (exists)
            sortedArrays[ai1].splice(i,1);
        }
      }
      // concat the remaining elements, they are all unique
      let output = sortedArrays[0];
      for(let i = 1; i < sortedArrays.length; i ++)
        output = output.concat(sortedArrays[i]);
        
      return output;
    }
    
    let arr1 = ['a', 'b', 'c', 'a', 'b']
    let arr2 = ['a', 'd', 'b', 'c']
    let arr3 = ['f', 'c', 'a']
    console.log(elementsInOnlyOneArr(arr1,arr2,arr3));
    
    

    看这个 JSFiddle:https://jsfiddle.net/4deq7xwm/
    更新 - 使用 splice() 替代 pop()

    这个返回了 ['a', 'f'] 而不是预期的 ['d', 'f']。我还没有深入研究实现原因。 - Scott Sauyet
    1
    谢谢@ScottSauyet,现在一切都解决了。我之前使用的是pop而不是splice来删除特定索引处的项目... - Chris Schaller

    4

    Array.prototype.includes() 方法似乎是这里的最佳选择。

    let arr1 = ['a', 'b', 'c', 'a', 'b']
    let arr2 = ['a', 'd', 'b', 'c']
    let arr3 = ['f', 'c', 'a', 'f']
    var arrays = [arr1,arr2,arr3];
    const items = arr1.concat(arr2, arr3);
    let results = [];
    
    items.forEach(isInOneArray);
    
    function isInOneArray(item){
      let found = 0;
      for (const arr of arrays){
        if (arr.includes(item)){
          found ++;
        }
      }
      if (found===1 && !results.includes(item)){
        results.push(item);
      }
    }
    console.log(results);


    6
    不要使用map来迭代数组,应该使用forEach。使用map而不是forEach会使代码变得难以阅读,因为map的目的是将数组映射到另一个数组。 - Donald Duck
    如果在 arr3 的末尾添加 'f',结果将是 ['d', 'f', 'f'],我相信这不是期望的结果。 - Scott Sauyet
    从技术上讲,结果满足要求。 - Ronnie Royston
    返回的元素不能重复。 - BurnsBA
    很好。通过添加 && !results.includes(item) 已经修复。 - Ronnie Royston

    3

    这个问题可以很容易地通过使用内置的.lastIndexOf()数组方法来解决:

    const arr1 = ['a', 'b', 'c', 'a', 'b'];
    const arr2 = ['a', 'd', 'b', 'c'];
    const arr3 = ['f', 'c', 'a'];
    
    function getValuesInOneArray(...arrays) {
      const combinedArr = arrays.flat();
      const result = [];
    
      for (const value of combinedArr) {
        if (combinedArr.indexOf(value) === combinedArr.lastIndexOf(value)) {
          result.push(value);
        }
      }
    
      return result;
    }
    
    getValuesInOneArray(arr1, arr2, arr3); // ['d', 'f']
    

    我通常会尽量避免使用“忍者代码”,以便于可维护性和可读性,但我无法抗拒将上述getValuesInOneArray()函数重写为更简洁的箭头函数。

    const getValuesInOneArray = (...arrays) =>
      arrays
        .flat()
        .filter(
          (value, index, array) => array.indexOf(value) === array.lastIndexOf(value)
        );
    

    你可以在Javacript.info这里阅读更多关于"忍者代码"(以及为什么应该避免使用它)的内容,但我建议在生产代码库中避免使用这样的做法。

    希望对你有所帮助。


    3
    创建一个由(x,y)对组成的集合,其中x是元素(在此情况下为字符串),y标识它来自的数组。首先按照x进行排序,时间复杂度为O(log n)(其中n是所有数组中的总项数)。遍历结果并检测所需项很容易。

    2
    function elementsInOnlyOneArr(arr1, arr2, arr3){
        let arr = arr1.concat(arr2).concat(arr3);
        return removeDuplicate(arr);
     }
    
     function removeDuplicate(arr){
       for(each of arr){
        let count = 0;
        for(ch of arr){
            if(each === ch){
                count++;
                if(count > 1){
                    //removing element that exist more than one 
                    arr = arr.filter(item => item !== each);
                    return removeDuplicate(arr);
                }
            }
        }
      }
        return arr;
     }
    
     let arr1 = ['a', 'b', 'c', 'a', 'b'];
     let arr2 = ['a', 'd', 'b', 'c'];
     let arr3 = ['f', 'c', 'a'];
     console.log(elementsInOnlyOneArr(arr1, arr2, arr3));
    

    -1
    对每个数组执行差异性分析,并将它们进行连接,以获取任意一个数组中唯一的值。

    const arr1 = ['a', 'b', 'c', 'a', 'b'];
    const arr2 = ['a', 'd', 'b', 'c'];
    const arr3 = ['f', 'c', 'a'];
    
    function diff(a1, a2, a3) {
      let u1 = a1.filter(el => { return !a2.includes(el) })
      .filter(el => { return !a3.includes(el) });
      let u2 = a2.filter(el => { return !a1.includes(el) })
       .filter(el => { return !a3.includes(el) });
       let u3 = a3.filter(el => { return !a2.includes(el) })
       .filter(el => { return !a1.includes(el) });
      return u1.concat(u2).concat(u3);
    }
    /* diff them */
    const adiff = diff(arr1, arr2, arr3);
    console.log(adiff);


    再看一遍,只需要对所有三个进行差异比较即可得到 OP 所需的 [ "d", "f"] - Mark Schultheiss
    2
    这在语义上与OP的逻辑类似,因此不太可能解决性能问题,这就是为什么你会得到一个负评。 - Chris Schaller
    3
    我不会给你点踩,但这种方法也不具备可扩展性。如果将数组数量增加到100个,你的代码会是什么样子呢? - exside

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接