谁用过online backup?# Hardware - 计算机硬件
s*r
1 楼
请问是不是find duplication和missing 的方法都是一样的
有n个数 range 是 [1, N-1],只有一个是duplication, 比如,N=4, {1,2,3,3}
方法:
1 数组全部加起来,和减去 1到N-1的和;
2 数组全部XOR, 然后依次XOR 1到 N-1;
3 二分法;
有 n-1 个数 range 是 [1, N],只有一个missing, 比如,N=4, {1,2,3}
方法:
1 全部 1到N,加起来,和减去数组的和;
2 数组全部XOR, 然后依次XOR 1到 N;
3 二分法;
有n个数 range 是 [1, N-1],只有一个是duplication, 比如,N=4, {1,2,3,3}
方法:
1 数组全部加起来,和减去 1到N-1的和;
2 数组全部XOR, 然后依次XOR 1到 N-1;
3 二分法;
有 n-1 个数 range 是 [1, N],只有一个missing, 比如,N=4, {1,2,3}
方法:
1 全部 1到N,加起来,和减去数组的和;
2 数组全部XOR, 然后依次XOR 1到 N;
3 二分法;