【LeetCode】丢失的数字 Java 题解
题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。
复制代码
思路分析
今天算法的每日一题是数组类题目。找出丢失的数字,这个题目并不难,可以应用高思求和公式求解。
高思求和公式文字表述:和 = (首项 + 末项)x 项数 / 2。常见的数学表达:1+2+3+4+……+ n = ( n + 1) * n /2。
结合本题,题目的数组是从 0 开始的,因此,我们可以讲高思定理转化为 count = (0 + n) * (n + 1) / 2,然后在将数组 nums 中的每一个元素减去,即可得到答案。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n),空间复杂度是 O(1)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/ea93d753cdc2f77a3bf4956ef】。文章转载请联系作者。
评论