计数未排序数组中的重复元素序列（Java）

Question

我需要一个函数来接收arrayList并返回一个新的arrayList，其中包含大小相同的整数。His元素将表示原始数组中索引i中的值的重复序列数（外观数）。

1单个外观也将被视为一个序列。例如：arr[1，1，0，1]-

• 输入：它不必是排序数组

函数示例：

arr[3,0,1,2,1,1,1,3]▪×输入：（arr）▪×输出：newArray[2,1,2,1,2,2,2,2]因为'3'在序列中出现2次，'0'出现1次，等等...

arr[1,0,1,2,1,3]▪×输入：（arr）▪×输出：newArray[3,1,3,1,3,1]

arr[1,0,0,2,1,3,0]▪︎ 输入：（arr）▪︎ 输出：newArray[2,2,2,1,2,1,2]

Answer 1

此任务类似于数组/列表中元素的常见计数频率，但相邻元素（子序列）应计为1。也就是说，当计数频率时，如果前一个元素与当前元素相同，则增量为0。

要使用Java流解决此任务，我们需要实现：

• 类来累加最终值和索引列表，包括添加索引和频率的方法

static class CollectorList {
    int sum;
    List<Integer> indexes = new ArrayList<>();
    
    public CollectorList(List<Integer> h) {
        this.indexes.add(h.get(0));
        this.sum += h.get(1);
    }
    
    public CollectorList merge(CollectorList next) {
        this.sum += next.sum;
        this.indexes.addAll(next.indexes);
        return this;
    }
}

然后，获取自定义频率列表的方法可以实现如下：

public static List<Integer> getFrequencyList(int ... arr) {
    return new ArrayList<>(
        IntStream.range(0, arr.length)  // stream of indexes
                 .mapToObj(i -> Map.entry(
                     arr[i],            // key: current element
                     Arrays.asList(i, i > 0 && arr[i] == arr[i - 1] ? 0 : 1))) // store index and delta
                 .collect(Collectors.toMap(
                     Map.Entry::getKey, // for array elements
                     e -> new CollectorList(e.getValue()), // init collector of helper 
                     CollectorList::merge   // and merge
                 ))
                 .values() // get Collection<CollectorList>
                 .stream() // convert CollectorList back to index -> frequency
                 .flatMap(c -> c.indexes.stream().map(i -> Map.entry(i, c.sum)))
                 .collect(Collectors.toMap(
                     Map.Entry::getKey, 
                     Map.Entry::getValue, 
                     (i1, i2) -> i1, TreeMap::new // sort by index
                 ))
                 .values() // frequencies by index
        );
}

为了简洁起见，上面的代码使用Java9Map.entry，它可以替换为构建new AbstractMap。如果需要Java8兼容性，SimpleEntry（）。

测试：

int[][] tests = {
    {},
    {0},
    {1,2,1,2,1,3,1},
    {1,1,0,1},
    {3,0,1,2,1,1,1,3},
    {1,0,1,2,1,3},
    {1,0,0,2,1,3,0}
};
for (int[] arr : tests) {
    List<Integer> result = getFrequencyList(arr);
    System.out.println(Arrays.toString(arr) + " -> " + result);
}

输出

[] -> []
[0] -> [1]
[1, 2, 1, 2, 1, 3, 1] -> [4, 2, 4, 2, 4, 1, 4]
[1, 1, 0, 1] -> [2, 2, 1, 2]
[3, 0, 1, 2, 1, 1, 1, 3] -> [2, 1, 2, 1, 2, 2, 2, 2]
[1, 0, 1, 2, 1, 3] -> [3, 1, 3, 1, 3, 1]
[1, 0, 0, 2, 1, 3, 0] -> [2, 2, 2, 1, 2, 1, 2]

Answer 2

您可以在O（n）时间复杂度中执行此操作：

步骤1：使用变量“prev”检查前一个元素，并将其初始化为false/0。步骤2：每当您找到要检查的元素时，就在数组中移动（比如x），若prev为false，则增加count，否则在数组中向前移动。