所以我有一个数组 A[1:n],其中包含从 1 到 n+1(包括 n+1)的随机唯一数字。任务是找到丢失的号码。通常你只需创建一个额外的数组 B[1:n+1] 并将数组 A 中的每个当前数字标记为数组 B 中的 1。 但是在这个问题中,数组 A 中的每个数字都以二进制代码作为字符串给出,我只能通过第 i 个字符串中的第 j 个符号访问 A 的元素 目标是想出一个复杂度为 O(n) 的算法
我的想法: 我想出了一个基于合并排序的算法,它会根据二进制代码中的第一个数字对每个字符串进行排序。但是复杂度是O(nlgn)
最佳答案
正如评论中所讨论的那样,如果只能逐位访问 A
的元素,则没有 O(n)
解决方案是可能的,因为必须读取所有位,并且每个数字中都有 log n
位。可以做到的最好的是 O(n log n)
。
也就是说,如果数组包含从 1 到 n+1
范围内的 n
个元素,并且正好缺少一个值,则可以通过取数组的总和,并将其与 n+1
的总和进行比较,由标准 formula 给出, (n+1)(n+2)/2
。
int n = 3;
String[] arr = {"001", "010", "100"};
int sum = 0;
for(int i=0; i<arr.length; i++)
for(int j=0, v=1; j<arr[i].length(); j++, v*=2)
if(arr[i].charAt(j) == '1') sum += v;
int m = (n+1)*(n+2)/2 - sum;
System.out.println("Missing: " + m);
输出:
Missing: 3
关于arrays - 递归算法题(缺数),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68739667/