javascript - 是两个数组的子集

Question

我想用一些测试用例得到两个数组的子集。我不想使用 javascript .every 函数，因为这太容易了。我的尝试有效，但我认为它不是时间和空间复杂度 O(n^2) 的最佳选择。

我的测试用例如下:

1) array1的所有值都应该在array2中定义

2) 如果array1 中存在重复值，它们也应该考虑到array2 中。例如，如果 arr1 = ["a", "a"] 和 arr2 = ["b", "a"] 那么 isSubset 为 false 因为 "a" 在第一个中出现了两次，而在第二个中只出现了一次。

这是我的解决方案:

let arr1 = ["A", "B", "C"];
let arr2 = ["C", "A", "B", "D"];

function isSubset(a, b) {
  if(a.length > b.length) {
    return false;
  }

  var myHash = {};
  for (var i = 0; i < a.length; ++i) {
    if(myHash[a[i]]) {
      myHash[a[i]] += 1;
    } else {
      myHash[a[i]] = 1;
    }
  }

  var myHash2 = {};
  for (var i = 0; i < b.length; ++i) {
    if(myHash2[b[i]]) {
      myHash2[b[i]] += 1;
    } else {
      myHash2[b[i]] = 1;
    }
  }


  for(var i in myHash) {
    for(var j in myHash2) {
      if(i == j && myHash[i] > myHash2[j]) {
        return false;
      }
    }
  }


  return true;
}

// test
var a = ["B", "A", "C", "A"];
var b = ["A", "B", "C", "D"];
var c = isSubset(a, b);
console.log(c);

代码笔:https://codepen.io/anon/pen/KYPayp?editors=0010

Answer 1

您不需要嵌套循环，因为您已经计算了 myHash2 中的计数。 .查一下吧。将嵌套循环替换为

for(var i in myHash) {
  if (myHash[i] > myHash2[i])
    return false;
}

时间复杂度为:O(n)，其中 n 是较大数组的长度。您还可以消除对 myHash2 的需求完全如果我们从 myHash 中减去计数器仅当 key 存在时(如 vivek_23 的 answer 中所示)

这也可以在 O(nlogn) + O(n) 中完成，其中 n是较大数组的长度不使用额外内存。 O(n log n) 用于排序。基本上，我们同时遍历两个数组并在元素相等的情况下递增指针。如果 arr2 中的元素更大，找不到元素，我们返回 false .如果我们到达 arr1 的末尾, 找到所有元素并返回 true .

function isSubset(arr1, arr2) {
  arr1 = arr1.sort();
  arr2 = arr2.sort();
  let idx1 = 0, idx2 = 0;
  while (idx1 < arr1.length) {
    if (idx2 >= arr2.length) {
      return false;
    }
    if (arr1[idx1] > arr2[idx2]) {
      idx2++;
    } else if (arr1[idx1] == arr2[idx2]) {
      idx1++; idx2++;
    } else {
      return false;
    }
  }
  return true;
}