以原始顺序从阵列和打印元素中移除唯一元素的算法

Question

有一个问题在困扰着我，不知何故，我无法弄清楚如何处理它。假设给出了一个数组{9,1,2,4,1,2,2}。阵列中的独特元素是9和4。输出数组应该是{1,2,1,2,2}。 我的想法是保留顺序并找到重复项，就是使用一个LinkedHashMap，它将有条目和条目的出现次数。

问题在于维护元素的顺序。一旦我把条目放入哈希映射中，顺序就会消失。

Answer 1

我会做这样的：

1. 创建

   HashMap的数量=新的HashMap（）;

2. 迭代您的阵列存储阵列值作为键和值的在HashMap中的计数作为值

3. 迭代阵列的第二时间和从数组中删除值，如果计数到键被一个。

Answer 2

没有什么会使阵列消失。只需遍历数组，检查映射中的值是否大于1。

Answer 3

因此，一个简单的方法是首先计算每个元素的数量（可以在O(n)中完成），迭代计数器并将count = 1的所有元素置于一个集合中（同样在O(n)中）。

现在运行原始列表并打印所有不在您设置的元素（也是O(n)）。所以解决方案将在O(n)时间和空间中运行。

这里是在Python 2号线的解决方案：

from collections import Counter 
arr = [9,1,2,4,1,2,2] 

unique = {k for k, v in Counter(arr).iteritems() if v == 1} 
print [i for i in arr if i not in unique] 

Answer 4

只是计数的元素，并检查当前元素的总数大于一。

代码示例（C++ 11）：

#include <iostream> 
#include <unordered_map> 
#include <vector> 

int main() { 
    std::vector<int> to_split = {9, 1, 2, 4, 1, 2, 2}; 

    std::vector<int> unique, not_unique; 
    std::unordered_map<int, int> counter; 
    for (int elem : to_split) { 
    ++counter[elem]; 
    } 
    for (int elem : to_split) { 
    if (counter[elem] > 1) { 
     not_unique.push_back(elem); 
    } else { 
     unique.push_back(elem); 
    } 
    } 

    std::cout << "Unique: " << std::endl; 
    for (int elem : unique) { 
    std::cout << elem << " "; 
    } 
    std::cout << std::endl; 
    std::cout << "Not unique:" << std::endl; 
    for (int elem : not_unique) { 
    std::cout << elem << " "; 
    } 
    std::cout << std::endl; 
    return 0; 
} 

输出：

Unique: 
9 4 
Not unique: 
1 2 1 2 2 

Answer 5

只是集思广益一点，但我无论如何都必须思考的一个不稳定的排序算法如何才能变得稳定：装饰，分类，展开。

根据您的输入列表，您可以遍历它，将项目的位置添加到地图中的列表中。

for (i = 0; i < length; i++) { 
    value = list[i] 
    map[value].append(i) 
} 

然后，删除所有项目进行计数1，并重建列表（你可以做，因为你必须在地图索引）。

进一步思考：为什么不只是做1循环计数，然后再建立过滤列表的循环？大概甚至有更好的表现，我认为O(n)。 （1迭代做计数，1次迭代重新构造新的列表）

Answer 6

类似fedekau的做法，但不包括：

int[]numbers = {9,1,2,4,1,2,2}; 
int guessedDistinct = (int)(2 * Math.sqrt(numbers.length)); 
final Map<Number, Boolean> 
    seenBefore = new HashMap<>(guessedDistinct); 
for (int i : numbers) 
    seenBefore.put(i, seenBefore.containsKey(i)); 
int[] out = Arrays.stream(numbers) 
    .filter(i -> seenBefore.getOrDefault(i, false)) 
    .toArray(); 
System.out.println(Arrays.toString(out)); 

（或尽量避免 “发现我两次” 填补seenBefore：

for (int i : numbers) 
    seenBefore.compute(i, (k, seen) -> null != seen);