首页 文章

用有效的算法计算数组中的相同对

提问于
浏览 次
5

Problem Statement ： a[] 是 n 数字的数组，计数为 . 在数组中相同的对，使得 0 <= p < q < n p，q是对的索引 .

a[3,5,6,3,3,5] n=6 这里相同对的数量为4，这是 (0,3), (0,4), (3,4), (1,5) 而不是（2,2）或（4,3）违反了 p < q 条件 .

Solution 1:

function getIdenticalPairs(a, n){
    var identicalPairs = 0;

    for(var i=0;i<n-1;i++){
       for(var j=i+1;j<n;j++){
         if(a[i]===a[j]){
           identicalPairs +=1;
        }
      }
   }
return identicalPairs;
}

这段代码工作正常，但似乎它的时间复杂度为O（n2） .

我试过的第二个解决方案是

Solution 2 ：使用组合公式，相同的nos，ncr对

var identicalPairs = 0;
function getIdenticalPairs(a, n){
  var map = {};  
  for(var i=0;i<n;i++){
​    if(map[a[i]]){
       map[a[i]].push(i);
    }else{
       map[a[i]] = [i];
    }
  }

 Object.keys(map).forEach(function(v,i){
    var occurances = map[v].length;
    if(occurances > 1){
       var nFact = factorial(occurances);
       var nrFact = factorial(occurances - 2);
       var rFact = factorial(2);
       //console.log(occurances , nFact, nrFact, rFact);
       identicalPairs += nFact/(nrFact*rFact)
   }
 })
​
 function factorial(n) { 
  if(n<=1) return 1; 
  var ret = 1;
  for(var i=2;i<=n;++i) 
    ret *= i;
  return ret; 
 } 
​
 return identicalPairs;
}

Q.1 我不确定但解决方案2的时间复杂度是否为O（n n n）= O（n）或O（n2）？

Q.2 如果它不是O（n）那么有一个更好的解决方案可能是时间复杂度O（nlogn）是 Javascript 还是 Java ？

javascript java arrays algorithm combinations

4 回答

  • 1

    将索引推入数组：

    Integer[] indices = new Integer[a.length];
for (int i = 0; i < a.length; ++i) indices[i] = i;

    根据 a 中相应元素的值对索引进行排序：

    Arrays.sort(indices, (i, j) -> Integer.compare(a[i], a[j]));

    然后从 indices 中拉出具有相同对应元素的索引块：

    int count = 0;
int i = 0;
while (i < indices.length) {
  int start = i;
  while (i < indices.length && a[indices[i]] == a[indices[start]]) {
    ++i;
  }

  // This is the number of indices whose corresponding values are equal.
  int thisCount = i - start;

  // This is the number of pairs you can make from
  // thisCount indices.
  int numPairs = thisCount * (thisCount - 1) / 2;

  count += numPairs;
}

    由于排序，这种方法总体上具有O（n log n）复杂度 . 组的计数是线性的 .

    Ideone demo

    回复于
  • 4

    计算数组中每个元素的出现次数：

    Map<Integer, Long> occurrences =
    IntStream.of(a).boxed().collect(
        Collectors.groupingBy(Function.identity(), Collectors.counting()));

    然后只计算每个键可以产生的对数：

    long count =
    occurrences.values().stream()
        .mapToLong(e -> e * (e - 1) / 2)
        .sum();

    这种方法总体上具有O（n）复杂度，因为插入哈希映射是恒定时间（并且这已经完成了n次），并且迭代映射的值是线性的 .

    Ideone demo

    回复于
  • 1

    这是典型的动态编程问题 . 您可以非常有效地执行以下操作;

    function indicesOfIdentical(a){
  return a.reduce((h,e,i) => (h[0][e] ? (h[1] = h[1].concat(h[0][e].map(n => [n,i])), h[0][e].push(i), h)
                                      :  h[0][e] = [i], h), [{},[]])[1];
}

var arr    = [0,3,5,6,3,3,5,0],
    result = indicesOfIdentical(arr);
console.log(JSON.stringify(result));
console.log("Test for 40 random items array of 0-9");
arr = Array(40).fill().map( _ => ~~(Math.random()*10));
result = indicesOfIdentical(arr);
console.log(JSON.stringify(arr));
console.log(JSON.stringify(result));
    回复于
  • 1

    您可以计算值并获得可能的组合计数 .

    • factorial 是获取数字的阶乘的函数

    • count 包含数组中元素的计数 .

    阶乘是获得n的所有组合和计数的必要条件，由于给定的规则，你只需要一半，索引应该是升序的 .

    function getCount(array) {
    var factorial = n => +!~-n || n * factorial(n - 1),
        count = array.reduce(
            (c, v) => (c[v] = (c[v] || 0) + 1, c),
            Object.create(null)
        );

    return Object
        .keys(count)
        .filter(k => count[k] > 1)
        .reduce((r, k) => r + factorial(count[k]) / 2, 0);
}

console.log(getCount([3, 5, 6, 3, 3, 5]));
    回复于

相关问题