文档章节

LeetCode:Missing Number - 缺失的数字

北风其凉
 北风其凉
发布于 2015/08/25 08:20
字数 459
阅读 2449
收藏 1

1、题目名称

Missing Number (缺失的数字)

2、题目地址

https://leetcode.com/problems/missing-number

3、题目内容

英文:Given an array containing n distinct numbers taken from 0, 1, 2, ..., n  find the one that is missing from the array.

中文:给出一个包含了n个不同数字的数组,从0开始一直到n,找出缺失的数字。如果数组是连续的则返回n+1。

例如:给出的数组为 [0, 1, 3] 则返回2

4、解题方法1

第一种方法是对原数组进行排序,然后使用一个计数用的变量按序考察排序后的数组,如果数组的第n位不等于n,则返回n,否则返回数组长度加一。

一段实现本方法的Java代码为:

import java.util.Arrays;

/**
 * 功能说明:LeetCode 268 - Missing Number
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月25日
 */
public class Solution {
    
    /**
     * 找出丢掉的数字
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {

        Arrays.sort(nums);
        int counter;
        for (counter = 0; counter < nums.length; counter++) {
            if (counter != nums[counter]) {
                return counter;
            }
        }
        return counter;
    }
}

5、解题方法2

第二种方法是建立一个新数组,长度为老数组的长度加一,新数组内的元素顺序排列。在老数组中每找到一个数字,都将新数组中对应位置变为-1,则最后新数组中未被变为-1的数字即为所求。

一段实现本方法的Java代码为:

/**
 * 功能说明:LeetCode 268 - Missing Number
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月25日
 */
public class Solution {
    
    /**
     * 找出丢掉的数字
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {

        int[] nums2 = new int[nums.length + 1];
        for (int i = 0; i < nums2.length; i++) {
            nums2[i] = i;
        }
        for (int i = 0; i < nums.length; i++) {
            nums2[nums[i]] = -1;
        }
        for (int i = 0; i < nums2.length; i++) {
            if (nums2[i] != -1) {
                return i;
            }
        }
        return -1;
    }
}

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 118
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
加载中

评论(1)

l
liang0000zai
这方法也太。。。。
LeetCode算法题-Missing Number(Java实现-四种解法)

这是悦乐书的第200次更新,第209篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第65题(顺位题号是268)。给定一个包含n个不同数字的数组,取自0,1,2,...,n,找到数组中缺少...

小川94
2018/12/13
0
0
268. Missing Number。

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array. Example 1 Input: [3,0,1] Output: 2 Example 2 Input: [9,6,4,......

Leafage_M
2018/01/08
0
0
Leetcode日记6

(2015/11/28) LeetCode 303 Range Sum Query - Immutable:(Easy) 1)超时的算法:每次调用sumRange函数进行一次累加运算。 2)不超时的算法:改变数组的内容,存储从0下标到当前下标所有...

fxdhdu
2015/11/28
73
0
LeetCode 268 Missing Number(丢失的数字)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50768898 翻译 原文 分析 因为数组可以是非常非常大,其大小并...

nomasp
2016/02/29
0
0
LeetCode 136 Single Number(只出现一次的数字)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50686403 翻译 原文 分析 请参照上一题:LeetCode 260 Single...

nomasp
2016/02/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

GatewayWorker 报错:stream_socket_server(): unable to connect to tcp://0.0.0.0:1238

GatewayWorker 报错:stream_socket_server(): unable to connect to tcp://0.0.0.0:1238 (Address already in use) 官方文档虽然有相同的问题,但是对我的问题没起作用…… 后面发现自己手贱...

wenzhizhong
昨天
0
0
REST接口

文章来源 https://zhuanlan.zhihu.com/p/28674721?group_id=886181549958119424 http://www.ruanyifeng.com/blog/2014/05/restful_api.html REST 对请求的约定 REST 用来规范应用如何在 HTTP......

Airship
昨天
3
0
Spring Cloud Config 统一配置中心

Spring Cloud Config 统一配置中心 一、统一配置中心 统一管理配置 通常,我们会使用配置文件来管理应用的配置。如一个 Spring Boot 的应用,可以将配置信息放在 application.yml 文件中,如...

非摩尔根
昨天
2
0
android ------ AAPT2 error: check logs for details解决方法

AAPT 是全称是 Android Asset Packaging Tool,它是构建 App,甚至是构建 Android 系统都必不可少的一个工具。它的作用是将所有资源文件压缩打包到Android APK 当中。我们在 Android SDK 目录...

切切歆语
昨天
2
0
今天的学习

今天学到了<select></select>标签: <label for="unittype">Select unit type: </label><select id="unittype" name="unittype" autofocus > <option value="1"> Miner </option> ......

墨冥
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部