一亩三分地论坛

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

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

[算法题] 有两个test cases过不去 - Find the Missing Number

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-22 16:57:13 | 显示全部楼层 |阅读模式

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

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

x

http://www.lintcode.com/en/problem/find-the-missing-number/

估计是time limit 超出了? 我觉得我代码思路没问题啊
  1. public class Solution {
  2.     /**   
  3.      * @param nums: an array of integers
  4.      * @return: an integer
  5.      */
  6.     public int findMissing(int[] nums) {
  7.         // write your code here
  8.         if(nums.length == 1)
  9.         {
  10.             return nums[0] + 1;
  11.         }
  12.         Arrays.sort(nums);
  13.         int sum = (nums[0] + nums[nums.length - 1]) * (nums.length + 1) / 2;
  14.         for(int i = 0; i < nums.length; i++)
  15.         {
  16.             sum -= nums[i];
  17.         }
  18.         return sum;
  19.     }
  20. }
复制代码
jusaka2012 发表于 2015-6-22 18:12:29 | 显示全部楼层
时间复杂度不对,java API的array sort用的是快排,时间复杂度是NlgN,题目要求N。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-22 18:14:21 | 显示全部楼层
jusaka2012 发表于 2015-6-22 18:12
时间复杂度不对,java API的array sort用的是快排,时间复杂度是NlgN,题目要求N。

challenge要求是o(n),好像不用达到也可以?

你有解法吗?谢谢
回复 支持 反对

使用道具 举报

jusaka2012 发表于 2015-6-22 18:32:50 | 显示全部楼层
love1point 发表于 2015-6-22 18:14
challenge要求是o(n),好像不用达到也可以?

你有解法吗?谢谢

NlgN>N,解法的话估计需要Bit Manipulation,但我没有刷这个题,所以你先试试看吧~~
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-22 18:37:09 | 显示全部楼层
jusaka2012 发表于 2015-6-22 18:32
NlgN>N,解法的话估计需要Bit Manipulation,但我没有刷这个题,所以你先试试看吧~~

多谢回复。和你讲的一样,网上有用bit manipulation的解法,
回复 支持 反对

使用道具 举报

iFighting 发表于 2015-6-22 19:22:16 | 显示全部楼层
给你看看我的代码。
  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: a vector of integers
  5.      * @return: an integer
  6.      */
  7.     int findMissing(vector<int> &nums) {
  8.         // write your code here
  9.         int len = nums.size();
  10.         for (int i = 0; i < len;) {
  11.             int cur = nums[i];
  12.             if (cur < len && nums[cur] != cur) {
  13.                 swap(nums[cur], nums[i]);
  14.             } else {
  15.                 i ++;
  16.             }
  17.         }
  18.         for (int i = 0; i < len; i ++) {
  19.             if (nums[i] != i) return i;
  20.         }
  21.         return len;
  22.     }
  23. };
复制代码
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-22 19:27:03 | 显示全部楼层
首先,你自己应该先仔细看清楚OJ到底提示什么错误。在这种情况下,OJ已经明确提示“Wrong Answer”了,所以就不要再往TLE那个方向去考虑。

其次,这段代码的逻辑有明显问题。你的想法应当是算0~N范围内所有值的和,所以应该用sum = (0 + N) * (N + 1) / 2这个公式。原程序的sum  = (A[0] + A[N-1]) * (N+1)/2这个公式则意义不明。似乎是想求数组中的元素和(实际上是不可能用公式求出的),但是长度N+1似乎又是想求0~N的和。看得出来你写这段代码时思路并不是很清晰。

再次,这种求sum的方法的缺陷是可能会溢出。其实完全没有必要求sum:既然已经排序过了,所以只要找到第一个“A[i]!=i”的位置即可。

最后,sort其实也是多余的。可以通过不断地“将每个数字交换到它应该出现的位置上”来达到O(N)的复杂度。CC150上有类似的题,给出的参考解法就是这种,你不妨找来参考。
回复 支持 反对

使用道具 举报

iFighting 发表于 2015-6-22 19:46:43 | 显示全部楼层
楼主你思路太不清晰了。。写代码之前至少应该确定算法的可行性以及正确性!
回复 支持 反对

使用道具 举报

cqx83 发表于 2015-6-23 04:21:32 | 显示全部楼层
iFighting 发表于 2015-6-22 03:46
楼主你思路太不清晰了。。写代码之前至少应该确定算法的可行性以及正确性!

小心伤了要毕业PhD的玻璃心,会被喷的体无完肤的。。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-23 08:24:58 | 显示全部楼层
stellari 发表于 2015-6-22 19:27
首先,你自己应该先仔细看清楚OJ到底提示什么错误。在这种情况下,OJ已经明确提示“Wrong Answer”了,所以 ...

我的思路如下:
假设输入数组为 [0, 1, 3]. 实际上要 [0 , 1, 2, 3]. 我的等差数列求和公式 的长度项 nums.length  + 1  是因为原数组的才3项,实际是要4项,所以我加了个1. 实际上我是求[0, 1, 2, 3]这四项和,然后减去[0, 1, 3],剩下的就是 缺失的一个 了 。

回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-23 08:25:11 | 显示全部楼层
iFighting 发表于 2015-6-22 19:46
楼主你思路太不清晰了。。写代码之前至少应该确定算法的可行性以及正确性!

我的思路如下:
假设输入数组为 [0, 1, 3]. 实际上要 [0 , 1, 2, 3]. 我的等差数列求和公式 的长度项 nums.length  + 1  是因为原数组的才3项,实际是要4项,所以我加了个1. 实际上我是求[0, 1, 2, 3]这四项和,然后减去[0, 1, 3],剩下的就是 缺失的一个 了 。

回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-23 10:21:01 | 显示全部楼层
jusaka2012 发表于 2015-6-22 18:32
NlgN>N,解法的话估计需要Bit Manipulation,但我没有刷这个题,所以你先试试看吧~~

感谢哈。

位运算的过了哈
  1. public class Solution {
  2.     /**   
  3.      * @param nums: an array of integers
  4.      * @return: an integer
  5.      */
  6.     public int findMissing(int[] nums) {
  7.         // write your code here
  8.         int sum = 0;
  9.         for(int i = 0; i < nums.length + 1; i++)
  10.         {
  11.             sum = sum ^ i;
  12.         }
  13.         int result = 0;
  14.         for(int i = 0; i < nums.length; i++)
  15.         {
  16.             result = result ^ nums[i];
  17.         }
  18.         result = result ^ sum;
  19.         return result;
  20.     }
  21. }
复制代码
回复 支持 反对

使用道具 举报

iFighting 发表于 2015-6-23 10:33:18 | 显示全部楼层
love1point 发表于 2015-6-23 10:21
感谢哈。

位运算的过了哈

当存在miss了多个不同的数的时候,你这个算法不通过。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-23 10:35:30 | 显示全部楼层
iFighting 发表于 2015-6-23 10:33
当存在miss了多个不同的数的时候,你这个算法不通过。

如果这种问题,有啥好解法吗
回复 支持 反对

使用道具 举报

iFighting 发表于 2015-6-23 10:36:44 | 显示全部楼层
love1point 发表于 2015-6-23 10:35
如果这种问题,有啥好解法吗

明显用我写的算法- -
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-23 10:38:54 | 显示全部楼层
iFighting 发表于 2015-6-23 10:36
明显用我写的算法- -

你这个也是一有一个missing的就退出程序了吧?
for (int i = 0; i < len; i ++) {

19.            if (nums != i) return i;

20.        }
回复 支持 反对

使用道具 举报

iFighting 发表于 2015-6-23 10:40:18 | 显示全部楼层
- -我的意思是当存在多个Miss的时候,我能正确找到,你用位运算的前提是只Miss了一个数。
另外,你用vector存下来不就好了么。
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-6-23 10:59:22 | 显示全部楼层
话说这个不是数学题么

public class Solution {
    /**   
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        int sum = 0;
        for(int i : nums){
            sum+=i;
        }
        
        int len = nums.length;
        return len*(len+1)/2 - sum;
    }
}



那个谁老师让他从1加到100来着
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-6-23 11:01:10 | 显示全部楼层
对了是高斯
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-23 11:02:55 | 显示全部楼层
2006reload 发表于 2015-6-23 10:59
话说这个不是数学题么

public class Solution {

最后两行代码是通过哪个数学式子想到的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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