c***g
发帖数: 472 | 1 一个unsorted的array, 包含1 - n的没有重复的整数
如果已经知道有n-1个, 只有一个missing, 怎么做, 这个加起来和xor就行了
如果已经知道只有n-2个, 只有两个missing, 怎么做, 1 到 n加起来, 算差, 1 到n的
平方, 加起来, 算差, 然后解方程.
这中间有人提到1到n的平方算和的时候会有overflow的问题, 怎么解决? 可以不可以
先算i的平方, 然后减去array[i]的平方, i从1到n求和, 这样就没有overflow了吧
如果已经知道有n-3个, 只有三个missing, 怎么做, 还是这样求三次方的和了再解方程
么?
还有别的办法么? | f****4
发帖数: 1359 | 2 如果已经知道有n-1个, 只有一个missing, 怎么做, 这个加起来和xor就行了
貌似n=2^m，才有把n-1个数全xor之后得到那个missing的数字啊 | m******9
发帖数: 968 | 3 你可以考虑用bitset, 遍历数组, 将所有出现的数在bitset中做好标记, 这个方法
可以找出任意个missing的数
也可以用swap的方法做, time o(n), space o(1)
我记得有个类似的的题目: 值域是1~n, 数组大小是n+m, 即有m个duplicate, 找出所有的
duplicate. | c***g
发帖数: 472 | 4 1 xor 2 xor .... xor n xor array[1] xor array[2] xor ...xor array[n]
【在 f****4 的大作中提到】
: 如果已经知道有n-1个, 只有一个missing, 怎么做, 这个加起来和xor就行了
: 貌似n=2^m，才有把n-1个数全xor之后得到那个missing的数字啊
| f****4
发帖数: 1359 | | s********a
发帖数: 1447 | 6 你是说 有n个数 their value 是from 1 to n
【在 c***g 的大作中提到】
: 一个unsorted的array, 包含1 - n的没有重复的整数
: 如果已经知道有n-1个, 只有一个missing, 怎么做, 这个加起来和xor就行了
: 如果已经知道只有n-2个, 只有两个missing, 怎么做, 1 到 n加起来, 算差, 1 到n的
: 平方, 加起来, 算差, 然后解方程.
: 这中间有人提到1到n的平方算和的时候会有overflow的问题, 怎么解决? 可以不可以
: 先算i的平方, 然后减去array[i]的平方, i从1到n求和, 这样就没有overflow了吧
: 如果已经知道有n-3个, 只有三个missing, 怎么做, 还是这样求三次方的和了再解方程
: 么?
: 还有别的办法么?
| I**A
发帖数: 2345 | 7
赞！这个bitset好。。
有的
【在 m******9 的大作中提到】
: 你可以考虑用bitset, 遍历数组, 将所有出现的数在bitset中做好标记, 这个方法
: 可以找出任意个missing的数
: 也可以用swap的方法做, time o(n), space o(1)
: 我记得有个类似的的题目: 值域是1~n, 数组大小是n+m, 即有m个duplicate, 找出所有的
: duplicate.
| m****n
发帖数: 589 | 8 这样可以知道有miss,还是可以知道miss的哪个?
应该是只知道有miss吧
【在 c***g 的大作中提到】
: 1 xor 2 xor .... xor n xor array[1] xor array[2] xor ...xor array[n]
| b******n
发帖数: 823 | 9 xor出来的结果就是miss的那个数
【在 m****n 的大作中提到】
: 这样可以知道有miss,还是可以知道miss的哪个?
: 应该是只知道有miss吧
| m****n
发帖数: 589 | 10 就是说只有n-1个? 那个miss掉的位置不会被其他的数字填掉,或者是重复?
【在 b******n 的大作中提到】
: xor出来的结果就是miss的那个数
| | | w******1
发帖数: 520 | 11 用XOR 的话，是找一堆重复数中的一个不重复吧？
如果是从1 到n 的升序， XOR 之后的结果没意义啊？
如果找打乱了排序的连续数中的丢掉的，或者多余的一个数， 求和就可以了。
但是， 如果不是一个数， 而是多个数， M 个， 那这方法行不通啊。 | T*****9
发帖数: 2484 | 12 求和可能会溢出
【在 w******1 的大作中提到】
: 用XOR 的话，是找一堆重复数中的一个不重复吧？
: 如果是从1 到n 的升序， XOR 之后的结果没意义啊？
: 如果找打乱了排序的连续数中的丢掉的，或者多余的一个数， 求和就可以了。
: 但是， 如果不是一个数， 而是多个数， M 个， 那这方法行不通啊。
| r****o
发帖数: 1950 | 13 hi, Teves99, 问一下，如果一个数组里面装的是double，还能用XOR这种办法吗？
【在 T*****9 的大作中提到】
: 求和可能会溢出
| T*****9
发帖数: 2484 | 14 当然不能
double自己本身就不精确
【在 r****o 的大作中提到】
: hi, Teves99, 问一下，如果一个数组里面装的是double，还能用XOR这种办法吗？
| r****o
发帖数: 1950 | 15 如果数组里面装的是字符串呢？可以用XOR吗?
【在 T*****9 的大作中提到】
: 当然不能
: double自己本身就不精确
| w******1
发帖数: 520 | 16 字符串AB 和AB XOR 之后， 是O 啊， 没问题吧
【在 r****o 的大作中提到】
: 如果数组里面装的是字符串呢？可以用XOR吗?
|
|
