leetCode算法-268（缺失数字）

geekzhou 发布于2019-08-23 15:06 / 1366人阅读

摘要：给定一个包含中个数的序列，找出中没有出现在序列中的那个数。求合法开始之前我先说一下我的思路个有序数字累加和，数学里边是有公式的，我们重温一下推导过程。

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2
示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

下面我用两种方法，一块了解一下。

求合法

         // 开始之前我先说一下我的思路
        //0-n个有序数字累加和，数学里边是有公式的，我们重温一下推导过程。
        // 0, 1          n为1 个数为2， 累加和为1
        // 0, 1, 2       n为2 个数为3，累加和为3
        // 0, 1, 2, 3    n为3 个数为4，累加和为6
        // 0, 1, 2, 3 ,4 n为4 个数为5， 累加和为10

        // 思考一下，n已知所以我们从n上找规律

        //以上我们推出 (n*个数)/2 = 累加和,是不是这个理？

        // n知道 累加和知道，少那个我们不就知道了吗？

        // 完整的n序列和-缺失数字的累加和=缺失数字

        // 翻译成代码
        var arr = [0, 1, 3]

        function findNum(nums) {
            let len = nums.length
            let n = len * (len + 1) / 2
            let n1 = nums.reduce((num, item) => {
                return num + item
            }, 0)
            console.log(n, n1)
            return n - n1
        };

        console.log(findNum(arr))//2

索引查找法

//先解析思路,0-n序列，数组的索引和0-n序列正好能一一对应，不过因为有可能是乱序，所以不能直接挨个匹配索引对比，我们需要换个思路。
//因为是序列，虽然乱序，只是和遍历n的索引值缺一个，这就简单了，我们通过遍历n来查找对应的剩余数组，找不到的就是我们要找的缺失数字，怎么找对应数字呢？你猜对了我们用indexOf()
          function findNum1(nums) {
            let len = nums.length + 1
            for (let i = 0; i < len; i++) {
                if (nums.indexOf(i) === -1) {
                    return i
                }
            }
        };
        findNum1(arr)

完美，只不过没有第一种的效率高！毕竟每一次indexOf也是一次遍历过程。

GPU云服务器云服务器数字水印算法数字图像识别算法图像识别数字算法 java数字阶层算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101513.html

LeetCode偶尔一题 —— 268. 缺失数字

摘要：题目描述给定一个包含中个数的序列，找出中没有出现在序列中的那个数。示例输入输出示例输入输出最简单的解法刚看到的这道题的时候，第一感觉就是排序，之后直接挨个比较就能找到缺失的数字。题目描述给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1: 输入: [3,0,1] 输出: 2 示例 2: 输入: [9,6,...

e10101 2019-08-26 10:22 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
70道前端LeetCode题目集合及视频讲解（持续更新中...）

前端LeetCode刷题下面是已刷的题目的目录。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，欢迎关注。数组类 26 删除排序数组中的重复项 27 移除元素 35 搜索插入位置 66 加1 80 medium 删除排序数组中的重复项2 88 合并两个有序数组 167 两数之和II - 输入有序数组 118 杨辉三角 169 easy 求众数 1...

mayaohua 2019-08-26 10:46 评论0 收藏0
leetcode 268 Missing Number

摘要：题目详情题目的意思是输入一个长度为的数组，找到这个数字中不存在于数组中的丢失的数字思路我的想法是，用这个数的和减去数组中的每一个元素的值，最后剩下的值就是丢失的数字解法题目详情 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing fr...

tianyu 2019-08-15 13:54 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0