f*********l
发帖数: 46 | 1 有个大小为n+1的数组，数组中的每个元素是[1,n]，所以至少有两个是重复的。例如n=
4, 数组为[2,3,4,1,1]或者[2,3,1,1,1]，要求找出重复的那个数字。复杂度要求：空
间O(1), 时间复杂度：小于O(n^2)。不能改变原来数组。
请各位看清题目再回复，和LC的题目不一样。 | d********t
发帖数: 9628 | 2 XOR?
n=
【在 f*********l 的大作中提到】
: 有个大小为n+1的数组，数组中的每个元素是[1,n]，所以至少有两个是重复的。例如n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1]，要求找出重复的那个数字。复杂度要求：空
: 间O(1), 时间复杂度：小于O(n^2)。不能改变原来数组。
: 请各位看清题目再回复，和LC的题目不一样。
| f*********l
发帖数: 46 | 3 能详细说说吗？
【在 d********t 的大作中提到】
: XOR?
:
: n=
| d********t
发帖数: 9628 | 4 不能，因为我也没做。
【在 f*********l 的大作中提到】
: 能详细说说吗？
| z****s
发帖数: 26 | | f*********l
发帖数: 46 | 6 哪个题目？我觉得不一样，如果有错误，请指正。
【在 z****s 的大作中提到】
: lc原题
| l*********u
发帖数: 19053 | 7 ＂不能改变原来数组＂，找到以后改回去，可以吗? :)
n=
【在 f*********l 的大作中提到】
: 有个大小为n+1的数组，数组中的每个元素是[1,n]，所以至少有两个是重复的。例如n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1]，要求找出重复的那个数字。复杂度要求：空
: 间O(1), 时间复杂度：小于O(n^2)。不能改变原来数组。
: 请各位看清题目再回复，和LC的题目不一样。
| b****h
发帖数: 2105 | 8 sum up, then you will get it
n=
【在 f*********l 的大作中提到】
: 有个大小为n+1的数组，数组中的每个元素是[1,n]，所以至少有两个是重复的。例如n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1]，要求找出重复的那个数字。复杂度要求：空
: 间O(1), 时间复杂度：小于O(n^2)。不能改变原来数组。
: 请各位看清题目再回复，和LC的题目不一样。
| d********t
发帖数: 9628 | 9 靠，考过这么多遍的我竟然都忘了。
【在 b****h 的大作中提到】
: sum up, then you will get it
:
: n=
| f*********l
发帖数: 46 | 10 不行
【在 l*********u 的大作中提到】
: ＂不能改变原来数组＂，找到以后改回去，可以吗? :)
:
: n=
| | | f*********l
发帖数: 46 | 11 看清题目再回答，还有楼下的那位。。。如果数组全是1,1,1,1,1，sum up 有啥用？
【在 b****h 的大作中提到】
: sum up, then you will get it
:
: n=
| j******3
发帖数: 16 | 12 压缩了空间，放宽了时间，感觉一定是divide & conquer，最后答案是O(nlogn)这样。
和xor 或者sum 应该没关系，这俩都是遍历出结果，O(n)时间。
有没有点提示？这个当follow up比较常见吧。 | b******b
发帖数: 713 | 13 binary search,
int lowbound = 0, uppbound =n;
int mid = (lowbound + uppbound) / 2;
int countLowHalf=0, countUpperHalf = 0;
now go through the list and count how many in lower half, how many in
upperhalf, and update the low/upper bound to the part which has count > n/2.
since each time we reduce the range by 2, so need longn steps to get to the
bottom, and each step need to loop through the whole array, so it's nlogn.
not sure if there is O(n) algorithm.
n=
【在 f*********l 的大作中提到】
: 有个大小为n+1的数组，数组中的每个元素是[1,n]，所以至少有两个是重复的。例如n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1]，要求找出重复的那个数字。复杂度要求：空
: 间O(1), 时间复杂度：小于O(n^2)。不能改变原来数组。
: 请各位看清题目再回复，和LC的题目不一样。
| n*******s
发帖数: 17267 | 14 排序， 然后一个一个比较不就完了， 这题考个Bird？ | b******b
发帖数: 713 | 15 cannot change the content of array, and O(1) space.
【在 n*******s 的大作中提到】
: 排序， 然后一个一个比较不就完了， 这题考个Bird？
| n*******s
发帖数: 17267 | 16 那就只能二分把N方降下来， 不过这纯属扯淡， 现在都什么年代还考怎么套牛拉车。
【在 b******b 的大作中提到】
: cannot change the content of array, and O(1) space.
| b****h
发帖数: 2105 | 17 没看清题，很简单，还是sum up, 先取<=n/2的，如果都出现且一次那么和是定值，那
么重复的一定是在>n/2中。每次遍历数组n, 遍历log n。复杂度nlogn
【在 f*********l 的大作中提到】
: 看清题目再回答，还有楼下的那位。。。如果数组全是1,1,1,1,1，sum up 有啥用？
| x*******9
发帖数: 138 | |
|
