JavaScript中比较单个数组项的最有效方法

Question

我有一个整数数组，例如：const foo = [2,5,6,2...]

我想创建一个函数来比较所有的项，如果其中一项恰好是另一项的两倍，则返回true，如果没有找到这样的情况，则返回false。

我首先想到的方法是做这样的事：

function foo(arr) {
    for(let ind = 0; ind < arr.length; ind++) {
        for( j = 1; j < arr.length; j++) {
        /// CHECK IF ITEM arr[ind] is double of arr[j] or viceversa and return true
        }
    }
    return false
}

这显然是一个相当糟糕的解决方案，因为它要多次遍历每个项。在JS中解决这个问题最有效的方法是什么？

- greatTeacherOnizuka

---

一旦找到结果，您可以添加一个break。不确定是否有效，请始终从i的值开始嵌套for循环。 - Kanishk Tanwar

当然是重复的：就像其他100个问题一样... - trincot

可能是重复的[1]（https://dev59.com/w1UM5IYBdhLWcg3wKNyB），[2]（https://stackoverflow.com/questions/19901533/i-need-to-check-a-javascript-array-to-see-if-there-are-any-duplicate-values），... 更多 - trincot

而且 [10, 10, 5] 必须返回false。 - Mihai Alexandru-Ionut

@greatTeacherOnizuka，我给你提供了一个时间复杂度为O(N)的答案。 - Mihai Alexandru-Ionut

Answer 1

将 .map(Number) 用于转换为数字，以使检查变得更加容易。

如果提供的测试至少有一个条目通过，则 .some() 将返回 true - 也就是说，提供的数组 .include() 是否包含当前正在测试的元素的两倍的值。

const arrayA = ['2','5','6','2'];
const arrayB = ['2','5','4','3'];

function demo (array) {
  return array
    .map(Number)
    .some((ele, _, ori) => ori.includes(ele * 2));
}

console.log(demo(arrayA));
console.log(demo(arrayB));

- Shiny

---

你能提供一下你的解决方案的复杂度吗？ - Mihai Alexandru-Ionut

Answer 2

这是一个简单的版本，只有一个循环，利用了 array.includes()。一旦找到一个重复项，就立即返回结果。

const test1 = ['2','3','5','7'];
const test2 = ['2','3','4','8'];

const findDouble = values => {
    for (i = 0; i < values.length; i++) {
        //Convert value to an integer and multiply
        const doubleValue = parseInt(values[i]) * 2;

        // Match using string
        if (values.includes(doubleValue.toString())) {
            return true;
        }
    };
    return false;
}

console.log(findDouble(test1));
console.log(findDouble(test2));

- Ed Lucas

Answer 3

首先，您应该使用Number构造函数应用map方法，以获取一个数字数组。

foo = foo.map(Number);

不要使用两个for循环，而是只使用一个具有O(N)复杂度的循环。思路是需要遍历数组并将当前项添加到set结构中。

然后只需检查在某个时间是否使用set结构的has方法遇到了item * 2或item/2，其复杂度为O(1)符合this答案。

因此，最终的复杂度是O(n)，因为我们只对数组进行一次迭代。另外，作为一种替代方案，您可以使用具有查询复杂度O(1)的hash结构（hasOwnProperty方法）。

myFunction = (arr) => {
  let set = new Set();
  for(i = 0; i < arr.length; i++){
      set.add(arr[i]);    
      if(set.has(arr[i] * 2) || set.has(arr[i]/2))
          return true;
  }
  return false;
}

console.log(myFunction([3,7,6,4, 2]));
console.log(myFunction([1,7,4,5,6]));

- Mihai Alexandru-Ionut

Answer 4

不要通过两次循环数组来计算数字出现的频率，而是要在单次遍历中计算。可以通过将数字分配给一个对象来实现，其中属性键是数字，值是出现的频率。

本质上，您希望最终得到类似于 {2:2, 5:1, 6:1 ....} 的东西。

然后，您可以使用 Object.values(obj) 来隔离值，并使用 .include(2) 查找是否有任何匹配项并返回布尔值。

const array = [5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 9]
const arrayTwo = [5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 9, 1, 1]

const exactlyXDupes = (arr,dupe) => {
    return (Object.values(arr.reduce((obj, num) => { obj[num] = (++obj[num] || 1); return obj }, {})).includes(dupe))
}

console.log(exactlyXDupes(array,2))
console.log(exactlyXDupes(arrayTwo,2))

- Thomas Ham

Answer 5

你可以使用JS对象来减少时间复杂度。

你可以创建一个对象，在遍历输入数组时，将对应于每个值的键设置为任何非空值。

之后遍历此对象的键，并检查在键数组中是否存在任何'n'，如果Object [2 * n]存在。

const foo = ["2", "5", "6", "2", "8", "4"];
const testObj = {};
let flag = 0;
foo.forEach(num => {
  if (testObj[2 * Number(num)]) {  // Test if double element exists already
    flag = 1;
  } else {
    testObj[num] = 1;
  }
});

if (flag !== 1) {
  const keyArray = Object.keys(testObj);
  keyArray.forEach(key => {
    if (testObj[2 * key]) {
      flag = 1;
    }
  });
}
console.log(flag === 1);

- Yash Agarwal