这是最近在Java技术访谈中向一位读者询问的编码问题。问题是从整数数组中删除重复项而不使用任何集合API类,如Set或LinkedHashSet,这可以使此任务变得微不足道。通常,如果您需要为任何项目工作执行此操作,我建议更好地使用Set接口,特别是LinkedHashSet,因为这也保持了将元素插入到Set中的顺序。仅从技术面试的角度来看,您需要使用循环或递归来执行此操作,具体取决于您最强的区域。在本文中,我正在分享一个幼稚的解决方案,它有很多限制,可以被视为生产质量代码,它不是最好的解决方案,但仍然是一个解决方案。
处理数组时主要问题不是找到重复项,而是删除它们。由于数组是静态的固定长度数据结构,因此无法更改其长度。这意味着,从数组中删除元素需要创建一个新数组并将内容复制到该数组中。
如果您的输入数组包含大量重复项,那么这可能会导致大量临时数组。它还增加了复制内容的成本,这可能非常糟糕。鉴于此限制,您需要制定一个策略来最小化内存和CPU要求。
Java程序从没有Collection的整数数组中删除重复项
在这个程序中,我们没有使用任何集合类来删除重复项,之前,我已经向您展示了一种从ArrayList中删除重复项的方法,它使用的是LinkedHashSet。如果面试官没有特别提及Collection,你仍然可以使用该解决方案。
您需要做的就是先将数组转换为ArrayList,然后再从该ArrayList创建一个LinkedHashSet。在这个例子中,我们通过不将它们复制到结果数组中来从数组中删除重复项,这个解决方案实际上不是删除重复项而是用默认值替换它,即零。
现在,让我们看看我们的Java解决方案,用于从整数数组中删除重复项:
import java.util.Arrays; |
这就是如何在不使用集合类的情况下从Java中删除重复数组的方法。正如我之前所说,这个解决方案并不完美,并且有一些严重的局限性,这是一个让您去发现的练习。我可以给出的一个提示是,数组本身可以包含作为重复项的默认值,例如0表示int,即使使用任何幻数,例如integer.max_值,也不能确定它们不会是输入的一部分。
关于从结果数组中永久删除重复项,一种方法可以是计算重复项的数量,然后创建一个大小正确的数组,即长度-重复项,然后将内容从中间结果数组复制到最终数组中,去掉标记为重复项的元素。