java - 用时间〜O(N)在数组中查找最大不可重复值
问题描述
我们如何在 ~O(N) 时间内找到数组中的最大不可重复值
我试图在很长一段时间内这样做,但我发现只有〜O(2N):
int solution(int[] A) {
List<Integer> arr = new ArrayList<Integer>();
Set<Integer> set = new HashSet<Integer>();
int max = 0;
for(int i = 0; i < A.length; i++) {
if(!set.add(A[i])) arr.add(A[i]);
}
for(int i = 0; i < A.length; i++) {
if (max < A[i] && !arr.contains(A[i])) max = A[i];
}
return max;
}
我们能不能快一点?!
解决方案
int A[] = {5, 5, 3, 2, 3, 1};
Map<Integer, Integer> map = new HashMap<>();
for(int i : A) {
Integer count = map.get(i);
// according to the comments
// map.merge(i, 1, Integer::sum)
map.put(i, count == null ? 1 : count + 1);
}
int max = 0;
for (Map.Entry<Integer, Integer> e : map.entrySet()) {
if (e.getValue() == 1 && max < e.getKey()) {
max = e.getKey();
}
}
System.out.println(max);
在这里,您将每个数字映射到它在数组中出现的次数。
在这种情况下,复杂度是 O(n)。
并且可能是最快的实现可能的整数
// this code for academic purpose only
// it can work only with integers less than
// 2^nextPowerOfTwo(array.lenght) as
// hash collision doesn't resolved
public static int nextPowerOfTwo(int value) {
value--;
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return ++value;
}
public static int findMaxUnique(int[] array) {
final int hashSize = nextPowerOfTwo(array.length);
final int[] hashArray = new int[hashSize];
for (int n : array) {
int hash = n ^ (n >>> 16);
hash &= hashSize - 1;
hashArray[hash]++;
}
int max = 0;
for (int n : array) {
int hash = n ^ (n >>> 16);
hash &= hashSize - 1;
if (hashArray[hash] == 1 && max < n) {
max = n;
}
}
return max;
}
public static void main(String[] args) {
int[] array = {5, 4, 5, 3, 1, 5, 4, 0};
System.out.println(findMaxUnique(array));
}
推荐阅读
- sql - 使用 Oracle12 中的合并技术在公用表中插入非重复值
- apache-spark - 使用 Spark Operator 在 Kubernetes 中启用多集群故障转移
- android - 无法连接到 Android 调试数据库,即使更改端口
- javascript - react-router-dom 'Link' 不仅适用于代码的一部分,而且在其他地方也能正常工作。有什么问题?
- c - 编写一个程序来检查给定字符串中每个 ASCII 值的相同字符的数量
- vbscript - VBS,从父子结构创建完整的层次结构字符串,递归
- excel - 用于比较两张纸之间的商店名称和发票编号并突出显示匹配的宏
- c++ - 使用 QNetworkReply 请求 POST 超时
- wordpress - ACF:如果用户不是帖子作者,则在 the_loop() 中未正确检索数据
- python - 变分自动编码器 (VAE) 返回一致的输出