📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4585| 回复: 45
跳转到指定楼层
上一主题 下一主题
收起左侧

有两个test cases过不去 - Find the Missing Number

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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. }
复制代码

上一篇:Career Cup第四轮刷题继续
下一篇:询问一道 Merge K Sorted List 题目的分析
推荐
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. };
复制代码
回复

使用道具 举报

推荐
 楼主| 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. }
复制代码
回复

使用道具 举报

推荐
 楼主| love1point 2015-6-23 11:07:24 | 只看该作者
全局:
2006reload 发表于 2015-6-23 10:59
话说这个不是数学题么

public class Solution {

我的解法,其实本质和你一样,但你过的去,我的过不去,求解
  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的解法,
回复

使用道具 举报

🔗
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],剩下的就是 缺失的一个 了 。

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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