对数组中的相似元素重新排序

Question

我有一个要求，需要将原始列表中的相似元素组合在一起。

例如：

I/P数组：

[1, 2, 3, A1, B1, 4, B2, 5, 6, C1, B3, B4, 7, 8, 9, 10, A2, A3, 11, 12, A4, C2, D1]

现在我想对以字母表开头的元素进行分组，这样属于特定字母表的所有元素都放在一起，并且将被放置在该字母表第一次出现之后。

O/P数组：

[1, 2, 3, A1, A2, A3, A4, B1, B2, B3, B4, 4, 5, 6, C1, C2, 7, 8, 9, 10, 11, 12, D1]

我想到的一个简单的解决方案是维护一个表示字母表及其元素的 HashMap，Map<Character, Queue<Element>> 并执行以下步骤：

遍历列表，如果遇到字母表，请执行以下操作之一：

1.1 如果地图中不存在字母表，将其添加到具有空队列的地图中，map.put('A', new LinkedList<>())

1.2如果map中存在该字母表，则将其从原列表中移除，加入其在map中对应的队列中，list.remove(element)和map.get('A').add(element)
再次遍历原始列表，当遇到字母表时，在其后立即从映射中添加其对应的队列。

我认为这个解决方案可行，但我不确定它是否可能会在边缘情况下失败或者它是否是最佳解决方案（即使它的复杂度是 O(n)）。

谁能提出更好的选择？

Answer 1

我认为是 O(n) 或接近的两阶段方法。

分析阶段：按照问题中的描述构建地图，但不要从数组中删除任何内容，因为这会导致元素移动并破坏 O(n)。
从旧列表构建一个新列表。对于旧列表中的每个元素：
1. 如果元素以字母（字母字符）开头，从映射中取出列表，将所有元素添加到新列表并从映射中删除条目 .如果在映射中没有找到条目，则表示它已被删除并添加到新列表中，所以什么都不做。
2. 否则只需将元素添加到新列表即可。
如果需要，将新列表的内容写回旧列表。

我对地图列表的首选是 ArrayList。如果重要，您可以进行自己的性能测量。

Answer 2

流API可用于这种情况：

在每个输入元素中按字母前缀或数字构建 LinkedHashMap 分组，并将具有相同前缀的元素收集到排序集中（或排序列表，如果可能重复）
获取步骤 1 的中间映射的值并使用 flatMap

String[] arr = {
    "1",  "2",  "3", "A1", "B1", "4", "B2",  "5",  "6", "C1", 
    "B3", "B4", "7", "8",  "9", "10", "A2", "A3", "11", "12", 
    "A4", "C2", "D1"
};

List<String> values = Arrays.stream(arr)
    .collect(Collectors.groupingBy(
        s -> s.matches("[A-Z]\d+") ? s.charAt(0) : s,
        LinkedHashMap::new,
        Collectors.mapping(s -> s, Collectors.toCollection(TreeSet::new))
    )).values().stream()
    .flatMap(TreeSet::stream)
    .collect(Collectors.toList());
System.out.println(values);

输出

[1, 2, 3, A1, A2, A3, A4, B1, B2, B3, B4, 4, 5, 6, C1, C2, 7, 8, 9, 10, 11, 12, D1]

Answer 3

这是一种与您描述的有点相似的方法：

数组的初始迭代：
1. 将所有字符串的索引存储在一个Set
2. 根据字符在Map>中存储索引
构建结果数组的最终迭代：
- 如果当前索引包含在上一组字符串索引中，且该字符尚未遇到，则插入Map>中引用的相关批次String，
- 否则直接插入到结果数组中。

public static String[] groupElements(String[] elements) {
    String[] groupedElements = new String[elements.length];
    Set<Integer> characterIndexes = new HashSet<>();
    Map<Character, List<Integer>> characterIndexesMap = new HashMap<>();
    for (int i = 0; i < elements.length; i++) {
        char firstCharacter = elements[i].charAt(0);
        if (Character.isLetter(firstCharacter)) {
            characterIndexes.add(i);
            if (!characterIndexesMap.containsKey(firstCharacter)) {
                List<Integer> newCharacterIndexes = new ArrayList<>();
                newCharacterIndexes.add(i);
                characterIndexesMap.put(firstCharacter, newCharacterIndexes);
            }
            else {
                characterIndexesMap.get(firstCharacter).add(i);
            }
        }
    }
    for (int i = 0, j = 0; i < elements.length && j < elements.length; i++) {
        if (!characterIndexes.contains(i)) {
            groupedElements[j++] = elements[i];
        }
        else {
            char firstCharacter = elements[i].charAt(0);
            if (!characterIndexesMap.containsKey(firstCharacter)) continue;
            List<Integer> indexes = characterIndexesMap.get(firstCharacter);
            for (int k = 0; k < indexes.size(); k++) {
                groupedElements[j + k] = elements[indexes.get(k)];
            }
            j += indexes.size();
            characterIndexesMap.remove(firstCharacter);
        }
    }
    return groupedElements;
}

编辑：上面使用 Streams API 的解决方案易于使用和理解，但与我发布的内容相比，它的性能成本很高。根据您的应用程序的需要使用任何一个。

对数组中的相似元素重新排序

Reordering similar elements within an array

java

arrays

algorithm

hashmap

data-structures