Happy New Year# Piebridge - 鹊桥
s*m
1 楼
给你一个数组,range[1,n]inclusive,然后说如果有个n+1的数组的话这里面有没
有重复?为什么?
pigeon hole principle
然后followup:怎么找到那个重复的数字?有可能有多个重复
继续followup;如果说不让你交换数字,即不能排序怎么办?可以用空间
继续followup:如果说没有空间怎么办?
这里用到了pigeon hole principle,二分查找
不懂最后一个followup,怎么用二分啊
--------------追加----------
这是别处看来的面经,
--pigeon hole principle,二分查找-- 是面试官的提示
----别人的回复,但我没看懂---
第二轮第二题不用空间, 是直接加起来arrray么。
恩,差不多吧,就是只要找到一个重复的就可以了所以用pigeon hole+二分每次能去掉
一半的范围
有重复?为什么?
pigeon hole principle
然后followup:怎么找到那个重复的数字?有可能有多个重复
继续followup;如果说不让你交换数字,即不能排序怎么办?可以用空间
继续followup:如果说没有空间怎么办?
这里用到了pigeon hole principle,二分查找
不懂最后一个followup,怎么用二分啊
--------------追加----------
这是别处看来的面经,
--pigeon hole principle,二分查找-- 是面试官的提示
----别人的回复,但我没看懂---
第二轮第二题不用空间, 是直接加起来arrray么。
恩,差不多吧,就是只要找到一个重复的就可以了所以用pigeon hole+二分每次能去掉
一半的范围