数组有N-2个数目字,数字的范围为1 . N,没有重复的元素,要求打印缺少的2个数字, 空间复杂度O(1)
数组有N-2个数字,数字的范围为1 ... N,没有重复的元素,要求打印缺少的2个数字, 空间复杂度O(1)。
数组有N-2个数字,数字的范围为1 ... N,没有重复的元素,要求打印缺少的2个数字, 空间复杂度O(1)。
这个题其实考察的是我们怎样用最少的辅助空间求出数组中缺少的两个数。其实可以通过数学思想解决这两个问题。
首先缺少的两个数假设是a和b,那如果我们能计算出a+b和a-b,自然就能计算出a和b的值,也就是数组中缺少的值。
那怎么得到a+b呢?我们一只N个中的N-2个那用N个和减去N-2个已知的数就可以了。
那怎么计算两个数的差值即a-b呢??
直接计算没思路,其实我们可以按照上面的思路,先计算出1……N的平方和,然后减去已知的N-2个数的平放,就得到了a*a+b*b了。
然后就可以得到a-b的平方再开放就ok了。
两个公式如下:
等差数列求和:sum=N(N+1)/2
连续自然数的平方和公式:N(N+1)(2N+1)/6
看看具体实现代码吧O(∩_∩)O哈哈~
上述代码由Java语言实现
数组有N-2个数字,数字的范围为1 ... N,没有重复的元素,要求打印缺少的2个数字, 空间复杂度O(1)。
这个题其实考察的是我们怎样用最少的辅助空间求出数组中缺少的两个数。其实可以通过数学思想解决这两个问题。
首先缺少的两个数假设是a和b,那如果我们能计算出a+b和a-b,自然就能计算出a和b的值,也就是数组中缺少的值。
那怎么得到a+b呢?我们一只N个中的N-2个那用N个和减去N-2个已知的数就可以了。
那怎么计算两个数的差值即a-b呢??
直接计算没思路,其实我们可以按照上面的思路,先计算出1……N的平方和,然后减去已知的N-2个数的平放,就得到了a*a+b*b了。
然后就可以得到a-b的平方再开放就ok了。
两个公式如下:
等差数列求和:sum=N(N+1)/2
连续自然数的平方和公式:N(N+1)(2N+1)/6
看看具体实现代码吧O(∩_∩)O哈哈~
private static void find() { int[] A = new int[] { 1, 3, 4, 8, 7, 5, 6, 10, 11, 12 }; int n = A.length + 2; int sum = (n * (n + 1)) >> 1; int squareSum = sum * (2 * n + 1) / 3; for (int i = 0; i < A.length; i++) { sum -= A[i]; squareSum -= A[i] * A[i]; } int ASubB=(int) Math.sqrt(-(sum*sum)+2*squareSum); System.out.println(((sum + ASumB) >> 1)+ " and "+ ((sum - ASumB) >> 1)); }
上述代码由Java语言实现