Leetcode287. Find the Duplicate Number Follow up

JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

这个应该return low。。。

blackrose 发表于 2016-5-31 10:55
you need to sort first

应该不需要sort吧。。sort了也没错。。因为你是过一遍来判断所有的数里面有多少小于mid的。。

二楼的解法应该是对的，最后返回值写错了。

e453079612 发表于 2016-5-31 21:39
二楼最后返回的结果应该是low，不是nums[low]

是的，不好意思，习惯打成index了。谢谢纠正哈

jy_121 发表于 2016-5-31 23:58
二楼的解法应该是对的，最后返回值写错了。

谢谢纠正，对的，返回值是low

JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

为什么low从1开始？

111180611 发表于 2016-6-1 02:01
为什么low从1开始？

这个low, high不是index,是nums里面的1到n的值，而nums.size()是n + 1

111180611 发表于 2016-6-1 02:01
为什么low从1开始？

从0开始应该也是对的。。因为不存在length小于2的情况。。
我的java代码这么写的，能过：
public int findDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        while (start<end){
            int mid = start+(end-start)/2;
            int count = 0;
            for (int num : nums){
                if (num<=mid) count++;
            }
            if (count>mid) end = mid;
            else start = mid+1;
        }
        return start;
    }

zpinthehouse 发表于 2016-6-1 02:25
从0开始应该也是对的。。因为不存在length小于2的情况。。
我的java代码这么写的，能过：
public int f ...

嗯，start是0，应该不影响