在arrays中找到2个缺失数字的最快方法
这个问题的存在只是因为纯粹的好奇心。 不是作业。
找到在数组1..n中找到两个缺失数字的最快方法
所以，在一篇相关的文章中： 在一组数字中找到缺失数字的最快方法我发现你可以通过总结和减去总数来快速完成这项工作。
但是2个数字怎么样？
所以，我们的选择是：
- 顺序搜索
- 总结项目，从1..n中的所有项目中减去总数，然后搜索所有可能的案例。
还要别的吗？ 可能有O（n）解决方案吗？ 我在其中一个网站的ruby部分找到了这个，但是考虑了任何语言（除非语言有一些特定的东西）
简单的方法（也很快:)
a = [1,2,3,5,7] b = (1..7).to_a p ba #=> [4, 6]
- 找到数字的总和
S=a1+...+an。 - 还找到平方和
T=a1*a1+...+an*an。 - 你知道总和应该是
S'=1+...+n=n(n+1)/2 - 你知道平方和应该是
T'=1^2+...+n^2=n(n+1)(2n+1)/6。 - 现在建立以下方程组
x+y=S'-S，x^2+y^2=T'-T。 - 通过写
x^2+y^2=(x+y)^2-2xy=>xy=((S'-S)^2-(T'-T))/2。 现在这些数字仅仅是z中的二次z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0的根：z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0。
假设数组为[1,4,2,3,7]。 缺少的数字是5,6
第1步：添加数组中的所有数字。 17.我们知道1..7（n *（n + 1）/ 2）= 28的总和。
因此x + y + 17 = 28 => x + y = 11
第2步：将数组中的所有数字相乘。 我们知道1..7 = 5040的乘积。
因此x * y * 168 = 5040 => x * y = 30
(x+y)^2 = x^2 + 2xy + y^2 => 121 = 60 + x^2 + y^2 => x^2 + y^2 = 61 (xy)^2 = x^2 - 2xy + y^2 => (xy)^2 = 61 - 60 => (xy)^2 = 1 => xy = 1
我们有x + y = 11和xy = 1。 解决x，y。
该解决方案不需要额外的存储空间，并且在O（n）中完成。
我通过以下方法获得了测试中最快的时间（比替换2个数组快一点）：
n = 10 input = [3, 6, 8, 2, 1, 9, 5, 7] temp = Array.new(n+1, 0) input.each { |item| temp[item] = 1 } result = [] 1.upto(n) { |i| result << i if temp[i] == 0 }
创建一组数字1到N.使用数组中的数字集计算此集合的差异。 由于数字不同，结果将是缺失的数字。 O(N)时间和空间。
如果你不知道数组中的数字是什么怎么办？ 如果您刚刚获得一个arrays并告知有一个数字丢失，但您不知道那里有什么数字，您可以使用此：
array = array.uniq.sort! # Just to make sure there are no dupes and it's sorted. i = 0 while i < n.length-1 puts n[i] + 1 if n[i] + 1 != n[i+1] i+=1 end
public class TwoNumberMissing { int fact(int x) { if (x != 0) return x * fact(x - 1); else return 1; } public static void main(String[] args) { TwoNumberMissing obj = new TwoNumberMissing(); int a[] = { 1, 2, 3, 4, 5 }; int sum = 0; int sum_of_ab = 0; for (int i = 0; i < a.length; i++) { sum = sum + a[i]; } int b[] = {4,5,3}; int prod = 1; int sum1 = 0; for (int i = 0; i < b.length; i++) { prod = prod * b[i]; sum1 = sum1 + b[i]; } int ab = obj.fact(a.length) / prod; System.out.println("ab=" + ab); sum_of_ab = sum - sum1; int sub_of_ab = (int) (Math.sqrt(sum_of_ab * sum_of_ab - 4 * ab)); System.out.println("sub_of_ab=" + sub_of_ab); System.out.println("sum_of_ab=" + sum_of_ab); int num1=(sum_of_ab+sub_of_ab)/2; int num2=(int)ab/num1; System.out.println("Missing number is "+num2+" and "+num1); } }
输出：
ab=2 sub_of_ab=1 sum_of_ab=3 Missing number is 1 and 2
我提出以下解决方案
#Swift上的二分法在数组中找到2个缺失的数字
private func find(array: [Int], offset: Int, maximal: Int, missing: Int) -> [Int] { if array.count <= missing + 1 { var found = [Int]() var valid = offset + 1 for value in array { if value != valid + found.count { found.append(valid) } valid += 1 } return found } let maxIndex: Int = array.count let maxValue: Int = maximal - offset let midIndex: Int = maxIndex / 2 let midValue: Int = array[midIndex - 1] - offset let lostInFirst: Int = midValue - midIndex let lostInSecond: Int = maxValue - maxIndex - lostInFirst var part1 = [Int]() var part2 = [Int]() if lostInFirst > 0 { let subarray = Array(array[0.. 0 { let subarray = Array(array[midIndex..
If the array is sorted from 0 to N then you can compare the difference with index. The recursion function for this is O(logN) Pseudo code for it is: // OffsetA will keep track of the index offset of our first missing Number // OffsetB will keep track of our second missing number // Both Offset are set to Zero on the first recursion call. Missing( Array A , Array B , OffsetA, OffsetB ){ Add Array's A and B together. Will call it array C.// At the beginning Array B would be empty. BaseCase: If array C.length is 2 return C M= C.length/2 // for the middle value. If (C[M] == M + OffsetA){ // This means that both the values that are missing are to the right side of the array. return Missing((Arrays.copyOfRange(C,M,C.length)),ArrayB,M + Of fsetA,OffsetB); } If (C[M] == M + OffsetA +2){// This means both our values are to the left side of the missing array return Missing((Arrays.copyOfRange(C,0,M)),ArrayB,OffsetA,OffsetB); } //This is the more complicated one. `If(C[M] == M + OffsetA + 1){` This means that their are values on both the left and right side of the array. So we have to check the the middle of the first half and the middle of the second half of the array and we send the two quarter parts into our Missing Function. The checks are pretty much the same as the if statements up top but you should be able to figure out them your self. It seems like a homework or interview question. EDIT: There might me a small issue with the offset switching and I dont have time to change it now but you should be able to figure out the basic concept. }
我喜欢总结并将结果与预期值进行比较的想法。 所以我的想法是将数组分成相等的部分，将它们加起来，看看双方是否都缺少一个数字。 如果一半是正确的，你可以迭代另一半（包含两个缺失的数字…..从语言学的角度来看听起来很错误。。<）直到你设法分开数字。
如果abs（ij）很大 – 或者说是单词：当缺失的数字彼此相距很远时，这种方法非常快。