优化代码以从给出差异的给定数字中查找组合总数？

Question

pairs 是 return 组合总数的函数，其差异为 k。

 static int pairs(int[] a,int k) {
   int counter=0;
   for (int i : a.length ) {
     for(int j=i+1;j<a.length;j++){
        if(a[i]-a[j]==k||a[i]-a[j]==-k){
            counter++;

         }
     }
  }

return counter;
}

a 是数字数组，k id 由 user.I 给出的数字差异必须找到差异为 k.I 的组合总数已经完成但是代码但是我想要更多优化代码。

Answer 1

你的解是数组大小的二次方。这是一个 class 包含四个具有不同特征的解决方案，所有解决方案都与输入的大小成线性关系，使用不同的中间数据结构重新排列输入数组以加快解决方案。

（现在我不得不希望这不是某些课程的练习。）

import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class KDiffer {
    /** Solution for a dense array without duplicates. */
    static int solutionDenseArrayUnique(int[] a, int k) {
        // determine lower and upper bound of array elements
        int lower = Integer.MAX_VALUE;
        int upper = Integer.MIN_VALUE;
        for (int e : a) {
            lower = Math.min(lower, e);
            upper = Math.max(upper, e);
        }
        // create bitset of correct size
        int size = upper - lower + 1;
        BitSet collect = new BitSet(size);
        // fill bitset with array elements
        for (int e : a) {
            collect.set(e - lower);
        }
        // check for elements at distance k
        int result = 0;
        for (int e = collect.nextSetBit(0); e >= 0; e =
                collect.nextSetBit(e + 1)) {
            if (collect.get(e + k)) {
                result++;
            }
        }
        return result;
    }

    /** Solution for a dense array with duplicates. */
    static int solutionDenseArrayDuplicate(int[] a, int k) {
        // determine lower and upper bound of array elements
        int lower = Integer.MAX_VALUE;
        int upper = Integer.MIN_VALUE;
        for (int e : a) {
            lower = Math.min(lower, e);
            upper = Math.max(upper, e);
        }
        // create target of correct size
        int size = upper - lower + 1;
        int[] collect = new int[size];
        // fill target with array elements
        for (int e : a) {
            collect[e - lower]++;
        }
        // check for elements at distance k
        int result = 0;
        for (int e : a) {
            if (e - lower + k < size) {
                result += collect[e - lower + k];
            }
        }
        return result;
    }

    /** Solution for a sparse array without duplicates. */
    static int solutionSparseArrayUnique(int[] a, int k) {
        // collect array elements into a set
        Set<Integer> collect = new HashSet<>();
        for (int e : a) {
            collect.add(e);
        }
        // check for elements at distance k
        int result = 0;
        for (int e : collect) {
            if (collect.contains(e + k)) {
                result++;
            }
        }
        return result;
    }

    /** Solution for a sparse array with duplicates. */
    static int solutionSparseArrayDuplicate(int[] a, int k) {
        // collect array elements into a multiset
        Map<Integer, Integer> collect = new HashMap<>();
        for (int e : a) {
            Integer count = collect.get(e);
            collect.put(e, count == null ? 1 : count + 1);
        }
        // check for elements at distance k
        int result = 0;
        for (Map.Entry<Integer, Integer> entry : collect.entrySet()) {
            Integer count = collect.get(entry.getKey() + k);
            if (count != null) {
                result += entry.getValue() * count;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = { 7, 5, 3, 4, 8, 10, 5, 7 };
        System.out.printf("Dense array, unique elements: %d%n",
                          solutionDenseArrayUnique(array, 2));
        System.out.printf("Sparse array, unique elements: %d%n",
                          solutionSparseArrayUnique(array, 2));
        System.out.printf("Dense array, duplicate elements: %d%n",
                          solutionDenseArrayDuplicate(array, 2));
        System.out.printf("Sparse array, duplicate elements: %d%n",
                          solutionSparseArrayDuplicate(array, 2));
    }
}

优化代码以从给出差异的给定数字中查找组合总数？

Optimizing code for finding total number of combination from given numbers whose difference is given?

java

complexity-theory