在数组中找到重复数字的问题，我的技术不好吗？

Question

我使用HashMap来存储每个元素的出现，然后遍历哈希图以获取重复的元素，但这个解决方案感觉不太对劲。

Firecode.io中的问题陈述：

编写一个方法duplicate来查找数组中重复的元素。该方法应该返回一个字符串中重复整数的列表，其中的元素按升序排序(如下所示)。

重复（{1,3,4,2,1}）--

重复（{1,3,4,2,1,2,4}）--

注意：您可以使用 toString（） 方法返回大多数数据结构的标准字符串表示形式，并使用 Arrays.sort（） 对结果进行排序。

这是我的代码：

 public String duplicate(int[] numbers) {
      HashMap < Integer, Integer > hs = new HashMap < Integer, Integer > ();
      for (int i = 0; i < numbers.length; i++) {
           if (hs.get(numbers[i]) == null) {
                hs.put(numbers[i], 1);
           } else hs.put(numbers[i], (Integer) hs.get(numbers[i]) + 1);
      }

      int size = 0;
      for (int i: hs.keySet()) {
           if (hs.get(i) > 1) {
                size++;
           }
      }
      int j = 0;
      int[] a = new int[size];
      for (int i: hs.keySet()) {
           if (hs.get(i) > 1) {
                a[j++] = i;
           }
      }

      Arrays.sort(a);
      return Arrays.toString(a);
 }

Answer 1

如果您使用的是Java 8或更高版本，您可以尝试：

public String duplicate(int[] numbers) {
    Map<Integer, Integer> hs = new HashMap<>();
    for ( int i : numbers ) {
        hs.merge( i, 1, Integer::sum);
    }
    return '[' + 
             hs.entrySet()
               .stream()
               .filter( e -> e.getValue() > 1 )
               .map(Entry::getKey)
               .sorted()
               .map(i -> i.toString())
               .collect(Collectors.joining(", ")) +
           ']';
}

Answer 2

由于您不必知道元素重复的次数，因此只需要一个 Set 来记住哪些元素是唯一的，哪些不是。如果您知道元素值（例如，介于 1 和 10 之间的数字），则可以进一步简化 Set to boolean[] 或位向量：

int[] numbers = {1, 3, 4, 2, 2, 1, 2, 4, 4};
Set<Integer> unique = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();
for (int n : numbers) {
    if (!unique.add(n)) {
        duplicates.add(n);
    }
}
List<Integer> result = new ArrayList<>(duplicates);
result.sort(Integer::compareTo);
System.out.println(result); // [1, 2, 4]

Answer 3

以下是我的做法：（出于教育目的的注释，可能不会在生产代码中包含它们。

public String duplicate(int[] numbers) {

  // holds the items we've encountered more than once.
  // TreeSet<> keeps things in sorted order for us.
  final SortedSet<Integer> duplicates = new TreeSet<>();

  // keeps track of items we've encountered.
  final Set<Integer> encountered = new HashSet<>(); 

  // iterate over every number
  for (final int number : numbers) {
    // Add the item to encountered. Set.add() will return true if 
    // the element is new to the set.
    if (!encountered.add(number)) {
       // Since the element wasn't new, ensure this item exists in the duplicates collection.
       duplicates.add(number);
    }
  }

  return duplicates.toString();
}