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

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

🔗
 楼主| 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] != 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 {

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

使用道具 举报

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

本版积分规则

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