题目:Problem description: You have an array A of size n – 1 containing numbers from 1 to n so there is one missing number, find it!
本文给出解决上述问题的两个方法。
方法一:求和然后相减
在这个方法中,首先求出1到n的和,可以使用数学公式int total = (n * (n + 1)) / 2;,然后求出给定数组中所有元素的和,两个值的差就是缺失的那个数。程序如下:
public class FindMissingNumber { public int findMethod1(int[] array, int n) { int total = (n * (n + 1)) / 2; int sum = 0; for (int i = 0, len = array.length; i < len; i++){ sum += array[i]; } return total - sum; } }
方法二:使用异或实现
在该方法中,先要知道异或的特性:
A B | A XOR B 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0
根据该特性,将会有如下的结果:
A ^ 0 = A A ^ A = 0 A ^ B = C C ^ A = B
所以,可以先将1到n做异或操作,得到的值再与给定数组中的所有元素进行异或操作,最后得到的那个数字就是缺失的那个数字。
基于这个思想,程序如下:
/** * A B | A XOR B * 0 0 | 0 * 0 1 | 1 * 1 0 | 1 * 1 1 | 0 * * @param array * @param n * @return */ public int findMethod2(int[] array, int n) { int result = 0; for(int i = 1; i <= n; i++){ result ^= i; } for(int i = 0, len = array.length; i < len; i++){ result ^= array[i]; } return result; }
测试程序和结果如下
public class FindMissingNumberTest { public static void main(String[] args) { FindMissingNumber finder = new FindMissingNumber(); int[] array = {1,2,3,4,6,7,8};//missing 5 System.out.println(finder.findMethod1(array, 8));//5 System.out.println(finder.findMethod2(array, 8));//5 } }
相关推荐
1-n中缺失2个数字,O(n)时间内找出它们 VS 2008环境
示例 1:输出:[6,6]解释:所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。示例 2:输出:[2,3,
给你一个未排序的整数数组nums,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。 示例1: 输入:nums=[1,2,0] 输出:3 本测试用例为测试超时用的超长用例...
1.以下程序打印出0~9的数字,请补充缺少的代码 ...下列方法的目的是,找出1~n之间所有的平方数。试补全缺失的代码。 当n=10时,输出结果是: 1 4 9 当n=100时,输出结果是: 1 4 9 16 25 36 49 64 81
physxloader.dll 是安装physx物理引擎后的一个dll文件,PhysX是N卡特有的物理加速模块,因为N卡在游戏界的影响力实在太大,所以现在基本大型的3D游戏运行时都需要这模块。 当运行程序或者游戏时,系统弹出错误提示...
编写一个有效的方法来检查一个数是否是 3 的倍数 7. 最右边设置位的位置 8. 找出出现奇数次的次数 136.单号 9.最大和连续子阵列 53. 最大子阵列 10. 找到缺失的数字(给定一个 n-1 个整数的列表,这些整数在 1 到 n ...
找出青蛙可以跳到河对岸的最早时间。 - 在应用所有交替操作后计算计数器的值:计数器加 1; 将所有计数器的值设置为当前最大值。 - 找出给定序列中不出现的最小正整数。 - 计算道路上过往车辆的数量。 - 从一系列 ...
线性回归找出拟合两个属性(变量)的最佳直线;多元线性回归涉及多个属性,将数据拟合到多维曲⾯ 下图即对数据进⾏线性回归拟合: 离群点: 2.1 离群点的分类 全局离群点:个别数据离整体数据较远 集体离群点:⼀组...
问题:H5py找不到 h5.pyx文件 此问题我理解为,在初始化h5py的时候,文件缺失,导致DLL; 无语。。 第一个想到的解决办法:重新安装H5py 这个办法没用。。。。 因为本人用的anaconda,已经卸载+重装N遍发现没用。 ...
找出和最小的 K 对 () 排序矩阵中的第 K 个最小元素 () 最长绝对文件路径 () 是子序列 () 分区相等子集总和 () 有效词方 () 最小基因突变 () 爆破气球的最少箭数 () 分配 Cookie () 重复子串模式 () 岛周长 () 加热...