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

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]

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

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

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

如果映射中存在字母表，那么将其从原始列表中删除，并将其添加到映射、list.remove(element)和list.remove(element)中的相应队列中。

1. 再次迭代原始列表，当遇到字母表时，在其后面从映射中添加相应的队列。

我认为这个解决方案会起作用，但我不确定它在边缘情况下是否会失败，或者它是否是最优的(即使它的复杂性是O(n))。

有人能提出更好的选择吗？

Answer 1

在这种情况下，可以使用流API：

flatMap

• 在每个输入元素中通过字母前缀或数字构建LinkedHashMap分组，并将具有相同前缀的元素收集到排序集(如果可能重复则为排序列表)，

• 获取步骤1的中间映射的值，并使用将集合/列表连接到单个列表/数组中。

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 2

一种我认为是O(n)或接近的两相方法。

1. 分析阶段:按照问题中的描述构建映射，但不要从数组中删除任何内容，因为这会导致元素移动和O(n)中断。
2. 将从旧列表中生成一个新列表。对于旧列表中的每个元素：
   1. ，如果元素以字母开头(字母字符)，从映射中取出列表，将所有元素添加到新列表中，并从映射中删除条目。如果在地图中没有找到条目，这意味着它已经被删除并添加到新列表中，所以nothing.
   2. Otherwise只是将元素添加到新的list.

中。

如果需要，请将新列表的内容写入旧列表.

1. .

我对地图中的列表的第一个选择是ArrayList。如果这很重要，你可以做你自己的性能测量。

Answer 3

以下是一种与您描述的方法有点类似的方法：

List>数组中的

1. 初始迭代：
   1. 存储集合中所有字符串的索引，
   2. 根据字符在Map

构造结果数组的最后一次迭代:如果当前索引包含在上一组字符串索引中，并且尚未遇到该字符，则插入在array.、List>、

• 中引用的相关的一批字符串，否则只需将其插入结果

• 中。

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的解决方案很容易使用和理解，但与我发布的内容相比，它的性能成本很高。根据应用程序的需要使用任何一种。