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_值，也不能确定它们不会是输入的一部分。
关于从结果数组中永久删除重复项，一种方法可以是计算重复项的数量，然后创建一个大小正确的数组，即长度-重复项，然后将内容从中间结果数组复制到最终数组中，去掉标记为重复项的元素。