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

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

🔗
 楼主| love1point 2015-6-23 11:04:21 | 只看该作者
全局:
love1point 发表于 2015-6-23 11:02
最后两行代码是通过哪个数学式子想到的?

明白了, (a1+ an) * n /2
回复

使用道具 举报

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

使用道具 举报

🔗
stellari 2015-6-23 11:08:21 | 只看该作者

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

全局:
本帖最后由 stellari 于 2015-6-23 11:34 编辑
love1point 发表于 2015-6-23 08:24
我的思路如下:
假设输入数组为 [0, 1, 3]. 实际上要 [0 , 1, 2, 3]. 我的等差数列求和公式 的长度项 nu ...


我知道,所以我才说楼主你思路不清晰啊。

你实际需要算的是(0 + N) * (N + 1) / 2,
而你现在用的是(A[0] + A[N-1]) * (N+1)/2。
所以只有当A[0] + A[N-1] == 0 + N时你的结果才正确。
如果缺失的数字不是0也不是N,那么确实总有A[0] = 0, A[N-1] = N,所以上式成立。
但是当确实的数字恰为0或N时,这式子可就不成立了,比如这个例子:

[0 1 2 3]

缺失的数字为4。用你原来的公式得到的结果则是(0 + 3) * (4 + 1) / 2 = 7.5=> 7.5 - 1 - 2 - 3 = 1.5.
回复

使用道具 举报

🔗
 楼主| love1point 2015-6-23 11:09:12 | 只看该作者
全局:
love1point 发表于 2015-6-23 11:07
我的解法,其实本质和你一样,但你过的去,我的过不去,求解

我明白了,我排序了
回复

使用道具 举报

🔗
 楼主| love1point 2015-6-23 11:10:00 | 只看该作者
全局:
过了
  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.         int sum = (0 + nums.length) * (nums.length + 1) / 2;
  13.         for(int i = 0; i < nums.length; i++)
  14.         {
  15.             sum -= nums[i];
  16.         }
  17.         return sum;
  18.     }
  19. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-6-23 12:45:26 | 只看该作者
全局:
stellari 发表于 2015-6-23 11:08
我知道,所以我才说楼主你思路不清晰啊。

你实际需要算的是(0 + N) * (N + 1) / 2,

(0 + 3) * (4 + 1) / 2 = shoule be 3
回复

使用道具 举报

🔗
 楼主| love1point 2015-6-23 12:46:41 | 只看该作者
全局:
stellari 发表于 2015-6-23 11:08
我知道,所以我才说楼主你思路不清晰啊。

你实际需要算的是(0 + N) * (N + 1) / 2,

数组的头和尾一定存在的啊,题目说的
Given an array contains N numbers of 0 .. N
回复

使用道具 举报

🔗
stellari 2015-6-23 13:33:55 | 只看该作者
全局:
本帖最后由 stellari 于 2015-6-23 13:35 编辑
love1point 发表于 2015-6-23 12:46
数组的头和尾一定存在的啊,题目说的
Given an array contains N numbers of 0 .. N


做题最忌脑补。原题的意思是“数组中含有0...N(这N+1个数)范围内的N个数,找出那个缺失的数”,只字未提“0和N一定在这个数组中”啊。你为什么会得出这个结论?
回复

使用道具 举报

🔗
 楼主| love1point 2015-6-23 17:20:47 | 只看该作者
全局:
stellari 发表于 2015-6-23 13:33
做题最忌脑补。原题的意思是“数组中含有0...N(这N+1个数)范围内的N个数,找出那个缺失的数”,只字 ...

不是我assume, 我按照这么做,代码可以ac
回复

使用道具 举报

🔗
stellari 2015-6-23 18:46:44 | 只看该作者
全局:
love1point 发表于 2015-6-23 17:20
不是我assume, 我按照这么做,代码可以ac

乱了哈,咱来捋一下:

你原来的代码是
(A[0] + A[N-1]) * ( N + 1) /2   -> 这是假设0和N-1都在数组中的情况 -> 没过

你后来的AC代码是
(0 + N) * (N + 1) /2 -> 这是没对数组做任何假设 -> 过了。

也就是说,“0和N-1都在数组中”这个假设让你写出了第一种代码,而第一种代码并没有通过。这说明,“0和N-1都在数组中”这个假设是不成立的。你后来是抛弃了这个假设才写出了AC的代码。



回复

使用道具 举报

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

本版积分规则

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