一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 375|回复: 8
收起左侧

[Leetcode] Help: wired output order problem in TwoSum sorted

[复制链接] |试试Instant~ |关注本帖
fishriver 发表于 2015-7-14 00:12:12 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
public class Test{

     public static void main(String []args){
         int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
         int target = 15;
         TwoSumSorted twoSumSorted = new TwoSumSorted();
         int[] solutions = twoSumSorted.twoSum(nums, target);
         int[] solutionsBi = twoSumSorted.twoSumBi(nums, target);
         
        System.out.printf("Solutions are %d and %d! \n", solutions[0], solutions[1]);
        System.out.printf("Binary Search method: Solutions are %d and %d! \n", solutionsBi[0], solutionsBi[1]);
     }
     
}

class TwoSumSorted{
    // binary search, time: O(nlogn), space: O(1)
    public int[] twoSumBi(int[] nums, int target){
        for(int i = 0; i < nums.length; i++){
            int diffIndex = biSearch(nums, target - nums[i]);
            if(diffIndex != -1){
                return new int[] {i + 1, diffIndex + 1};
            }
        }
        throw new IllegalArgumentException("No two sum solution exist");
    }
   
    private int biSearch(int[] nums, int target){
        int l = 0, h = nums.length - 1;
        while(l < h){
            int m = (l + h)/2;
            if(nums[m] < target){
                l = m + 1;
            }else if(nums[m] > target){
                h = m - 1;
            }else{
                return m;
            }
        }
        return -1;  // use this line will print 8, 7, why????
        //return nums[l] == target ? l : -1;  
    }
}
2006reload 发表于 2015-7-14 15:42:29 | 显示全部楼层
private int biSearch(int[] nums, int target){
        int l = 0, h = nums.length - 1;
        while(l <= h){
            int m = (l + h)/2;
            if(nums[m] < target){
                l = m + 1;
            }else if(nums[m] > target){
                h = m - 1;
            }else{
                return m;
            }
        }
        return -1;  // use this line will print 8, 7, why????
        //return nums[l] == target ? l : -1;  
    }
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-7-14 16:52:51 | 显示全部楼层
话说楼主这样写binary search 也是错的
回复 支持 反对

使用道具 举报

 楼主| fishriver 发表于 2015-7-15 02:17:51 | 显示全部楼层
2006reload 发表于 2015-7-14 15:42
private int biSearch(int[] nums, int target){
        int l = 0, h = nums.length - 1;
        whi ...

Thank you for your comments.
But I don't think <= make difference from <.
I'd love to hear your insight.
回复 支持 反对

使用道具 举报

 楼主| fishriver 发表于 2015-7-15 02:18:45 | 显示全部楼层
        return -1;  // use this line will print 8, 7, why????
The problem is this line. Why it will get 8 7 ?
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-7-15 14:57:35 | 显示全部楼层
  private int biSearch(int[] nums, int target){
        int l = 0, h = nums.length - 1;
        while(l < h){
            int m = (l + h)/2;
            if(nums[m] < target){
                l = m + 1;
            }else if(nums[m] > target){
                h = m - 1;
            }else{
                return m;
            }
        }
        return -1;  // use this line will print 8, 7, why????
        //return nums[l] == target ? l : -1;  
    }

这样写7可以找到但是8找不到
所以返回8,7
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-15 15:34:12 | 显示全部楼层
fishriver 发表于 2015-7-15 02:17
Thank you for your comments.
But I don't think

差别在于。如果只用<号的话的意思是“只要找到一个位置,这个位置一定满足条件”,<=号则是在“找到位置后,还要检查一下位置上的值是否==target才能断定是否满足条件”。有些应用里面,比如“Search Insert Position”等就是“找到的肯定是能够插入的位置”。但是在这个楼主给定的情况下则必须确认最后找到的那个值是满足条件的。如果不用等于号,就必须在循环外多加一个判断。
回复 支持 反对

使用道具 举报

 楼主| fishriver 发表于 2015-7-22 04:21:26 | 显示全部楼层
2006reload 发表于 2015-7-15 14:57
private int biSearch(int[] nums, int target){
        int l = 0, h = nums.length - 1;
        wh ...

Thank you.
回复 支持 反对

使用道具 举报

 楼主| fishriver 发表于 2015-7-22 04:21:42 | 显示全部楼层
stellari 发表于 2015-7-15 15:34
差别在于。如果只用

Thank you!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 22:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表