arrays - 递归算法题(缺数)

Question

所以我有一个数组 A[1:n]，其中包含从 1 到 n+1(包括 n+1)的随机唯一数字。任务是找到丢失的号码。通常你只需创建一个额外的数组 B[1:n+1] 并将数组 A 中的每个当前数字标记为数组 B 中的 1。但是在这个问题中，数组 A 中的每个数字都以二进制代码作为字符串给出，我只能通过第 i 个字符串中的第 j 个符号访问 A 的元素目标是想出一个复杂度为 O(n) 的算法

我的想法:我想出了一个基于合并排序的算法，它会根据二进制代码中的第一个数字对每个字符串进行排序。但是复杂度是O(nlgn)

Answer 1

正如评论中所讨论的那样，如果只能逐位访问 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