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

19-01-23 banq
         

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

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

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

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

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

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

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

import java.util.Arrays;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 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
 */
public class TechnicalInterviewTest {

    private static final Logger logger = LoggerFactory.getLogger(TechnicalInterviewTest.class);

    public static void main(String args[]) {

        int[][] test = new int[][]{
            {1, 1, 2, 2, 3, 4, 5},
            {1, 1, 1, 1, 1, 1, 1},
            {1, 2, 3, 4, 5, 6, 7},
            {1, 2, 1, 1, 1, 1, 1},};

        for (int[] input : test) {
            System.out.println("Array with Duplicates       : " + Arrays.toString(input));
            System.out.println("After removing duplicates   : " + Arrays.toString(removeDuplicates(input)));
        }
    }

    /*
     * 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.
     */
    public static int[] removeDuplicates(int[] numbersWithDuplicates) {

        // Sorting array to bring duplicates together      
        Arrays.sort(numbersWithDuplicates);     
      
        int[] result = new int[numbersWithDuplicates.length];
        int previous = numbersWithDuplicates[0];
        result[0] = previous;

        for (int i = 1; i < numbersWithDuplicates.length; i++) {
            int ch = numbersWithDuplicates[i];

            if (previous != ch) {
                result[i] = ch;
            }
            previous = ch;
        }
        return result;

    }
}

Output :
Array with Duplicates       : [1, 1, 2, 2, 3, 4, 5]
After removing duplicates   : [1, 0, 2, 0, 3, 4, 5]
Array with Duplicates       : [1, 1, 1, 1, 1, 1, 1]
After removing duplicates   : [1, 0, 0, 0, 0, 0, 0]
Array with Duplicates       : [1, 2, 3, 4, 5, 6, 7]
After removing duplicates   : [1, 2, 3, 4, 5, 6, 7]
Array with Duplicates       : [1, 2, 1, 1, 1, 1, 1]
After removing duplicates   : [1, 0, 0, 0, 0, 0, 2]

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

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