转载

如何在不使用Java Collection API的情况下从数组中删除重复项

这是最近在Java技术访谈中向一位读者询问的编码问题。问题是从整数数组中删除重复项而不使用任何集合API类，如Set或LinkedHashSet，这可以使此任务变得微不足道。通常，如果您需要为任何项目工作执行此操作，我建议更好地使用Set接口，特别是LinkedHashSet，因为这也保持了将元素插入到Set中的顺序。仅从技术面试的角度来看，您需要使用循环或递归来执行此操作，具体取决于您最强的区域。在本文中，我正在分享一个幼稚的解决方案，它有很多限制，可以被视为生产质量代码，它不是最好的解决方案，但仍然是一个解决方案。

处理数组时主要问题不是找到重复项，而是删除它们。由于数组是静态的固定长度数据结构，因此无法更改其长度。这意味着，从数组中删除元素需要创建一个新数组并将内容复制到该数组中。

如果您的输入数组包含大量重复项，那么这可能会导致大量临时数组。它还增加了复制内容的成本，这可能非常糟糕。鉴于此限制，您需要制定一个策略来最小化内存和CPU要求。

Java程序从没有Collection的整数数组中删除重复项

在这个程序中，我们没有使用任何集合类来删除重复项，之前，我已经向您展示了一种从ArrayList中删除重复项的方法，它使用的是LinkedHashSet。如果面试官没有特别提及Collection，你仍然可以使用该解决方案。

您需要做的就是先将数组转换为ArrayList，然后再从该ArrayList创建一个LinkedHashSet。在这个例子中，我们通过不将它们复制到结果数组中来从数组中删除重复项，这个解决方案实际上不是删除重复项而是用默认值替换它，即零。

现在，让我们看看我们的Java解决方案，用于从整数数组中删除重复项：

[b]<b>import</b>[/b] [b]java.util.Arrays[/b];
<p>[b]<b>import</b>[/b] [b]org.slf4j.Logger[/b];
<p>[b]<b>import</b>[/b] [b]org.slf4j.LoggerFactory[/b];
<font><i>/**
 * Java program to remove duplicates from this array. You don't
 * need to physically delete duplicate elements, replacing with null, or
 * empty or default value is ok.
 *
 * @author http://javarevisited.blogspot.com
 */</i></font><font>
<p>[b]<b>public</b>[/b] [b]<b>class</b>[/b] [b]TechnicalInterviewTest[/b] {
    [b]<b>private</b>[/b] [b]<b>static</b>[/b] [b]<b>final</b>[/b] Logger logger = LoggerFactory.getLogger(TechnicalInterviewTest.<b>class</b>);
    [b]<b>public</b>[/b] [b]<b>static</b>[/b] [b]<b>void</b>[/b] [b]main[/b](String args[]) {
        [b]<b>int</b>[/b][][] test = [b]<b>new</b>[/b] [b]<b>int</b>[/b][][]{
            {[b]1[/b], [b]1[/b], [b]2[/b], [b]2[/b], [b]3[/b], [b]4[/b], [b]5[/b]},
            {[b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b]},
            {[b]1[/b], [b]2[/b], [b]3[/b], [b]4[/b], [b]5[/b], [b]6[/b], [b]7[/b]},
            {[b]1[/b], [b]2[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b]},};
        [b]<b>for</b>[/b] ([b]<b>int</b>[/b][] input : test) {
            System.out.println(</font><font>"Array with Duplicates       : "</font><font> + Arrays.toString(input));
            System.out.println(</font><font>"After removing duplicates   : "</font><font> + Arrays.toString(removeDuplicates(input)));
        }
    }
    </font><font><i>/*
     * Method to remove duplicates from array in Java, without using
     * Collection classes e.g. Set or ArrayList. Algorithm for this
     * method is simple, it first sort the array and then compare adjacent
     * objects, leaving out duplicates, which is already in the result.
     */</i></font><font>
    [b]<b>public</b>[/b] [b]<b>static</b>[/b] [b]<b>int</b>[/b][] [b]removeDuplicates[/b]([b]<b>int</b>[/b][] numbersWithDuplicates) {
        </font><font><i>// Sorting array to bring duplicates together      </i></font><font>
        Arrays.sort(numbersWithDuplicates);     
      
        [b]<b>int</b>[/b][] result = [b]<b>new</b>[/b] [b]<b>int</b>[/b][numbersWithDuplicates.length];
        [b]<b>int</b>[/b] previous = numbersWithDuplicates[[b]0[/b]];
        result[[b]0[/b]] = previous;
        [b]<b>for</b>[/b] ([b]<b>int</b>[/b] i = [b]1[/b]; i < numbersWithDuplicates.length; i++) {
            [b]<b>int</b>[/b] ch = numbersWithDuplicates[i];
            [b]<b>if</b>[/b] (previous != ch) {
                result[i] = ch;
            }
            previous = ch;
        }
        [b]<b>return</b>[/b] result;
    }
}
<p>[b]Output :[/b]
Array with Duplicates       : [[b]1[/b], [b]1[/b], [b]2[/b], [b]2[/b], [b]3[/b], [b]4[/b], [b]5[/b]]
After removing duplicates   : [[b]1[/b], [b]0[/b], [b]2[/b], [b]0[/b], [b]3[/b], [b]4[/b], [b]5[/b]]
Array with Duplicates       : [[b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b]]
After removing duplicates   : [[b]1[/b], [b]0[/b], [b]0[/b], [b]0[/b], [b]0[/b], [b]0[/b], [b]0[/b]]
Array with Duplicates       : [[b]1[/b], [b]2[/b], [b]3[/b], [b]4[/b], [b]5[/b], [b]6[/b], [b]7[/b]]
After removing duplicates   : [[b]1[/b], [b]2[/b], [b]3[/b], [b]4[/b], [b]5[/b], [b]6[/b], [b]7[/b]]
Array with Duplicates       : [[b]1[/b], [b]2[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b], [b]1[/b]]
After removing duplicates   : [[b]1[/b], [b]0[/b], [b]0[/b], [b]0[/b], [b]0[/b], [b]0[/b], [b]2[/b]]
</font>

这就是如何在不使用集合类的情况下从Java中删除重复数组的方法。正如我之前所说，这个解决方案并不完美，并且有一些严重的局限性，这是一个让您去发现的练习。我可以给出的一个提示是，数组本身可以包含作为重复项的默认值，例如0表示int，即使使用任何幻数，例如integer.max_值，也不能确定它们不会是输入的一部分。

关于从结果数组中永久删除重复项，一种方法可以是计算重复项的数量，然后创建一个大小正确的数组，即长度-重复项，然后将内容从中间结果数组复制到最终数组中，去掉标记为重复项的元素。

原文 https://www.jdon.com/51550

正文到此结束