整数宇宙映射阵列在定域映射中的应用与实现

Question

假设您被赋予整数数组，它可以占用整个整数空间。但是，我想把它映射到固定范围。

For ex: {1, 5, 38, 5, 2^32-1} ---> {1, 2, 3, 2, 4}请注意重复的元素值'5‘和它的映射数组。阶不相关。

除了芬威克树(芬威克树要求范围为1.N)外，是否还有其他应用？

一种方法是这样做，

int[] map( int[]  a) {
    int[] transArr = new int[a.length];
    Map<Integer,Integer> posValueMap = new HashMap<Integer,Integer>();
    for(int i= 0 ; i < a.length; i++) {
       if(!posValueMap.contains(i))
          posValueMap.put(a[i], i);
    }
    for(int i= 0 ; i < transArr.length; i++) {
        transArr[i] = posValueMap.get(a[i]);
    }
    return transArr;
}

是否有更简单的方法可以使用不同的算法或函数式编程构造来实现这一点？

Answer 1

看来你需要某种完美散列。

极小完美散列函数将N个不同元素的集合映射到范围0.n-1或1..N范围内的N个整数键，如您所需。

(有用于MPH的开源库)