[Swift]LeetCode268. 缺失数字 | Missing Number

发布时间：2020-12-14 05:11:10 所属栏目：百科来源：网络整理

导读：? 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,1]Output: 2 Example 2: Input: [9,6,4,3,5,7,1]Output: 8 Note: Your algorithm should run in linear ru

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,1]
Output: 2

Example 2:

Input: [9,6,4,3,5,7,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

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

示例 1:

输入: [3,1]
输出: 2

示例?2:

输入: [9,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

 1 class Solution {
 2     func missingNumber(_ nums: [Int]) -> Int {
 3         //利用异或运算，将数组全体内容与0~n进行异或, 4         //根据异或运算的性质可知最后结果为缺少的那个数字。
 5         var result:Int = nums.count
 6         for i in 0..<nums.count
 7         {
 8             result ^= i ^ nums[i]
 9         }
10         return result        
11     }
12 }

28ms

1 class Solution {
2     func missingNumber(_ nums: [Int]) -> Int {
3         var h = (nums.count+1)*nums.count/2
4         for i in 0..<nums.count {
5            h -= nums[i]
6         }
7         return h
8     }
9 }

24ms

 1 class Solution {
 2     func missingNumber(_ nums: [Int]) -> Int {
 3         var sum = 0 
 4         var max = 0
 5         var i = 0
 6         while i < nums.count {
 7             max = max + i
 8             sum = sum + nums[i]
 9             i = i + 1
10         }
11         return max - sum + i
12     }
13 }

32ms：

求出从0~n的累加和，减去数组整体的和，那么由于数组内每个数字不相同，其差就是缺少的那个数字

 1 class Solution {
 2     func missingNumber(_ nums: [Int]) -> Int {
 3         let count = nums.count
 4         var sum = count + (count * (count - 1)) / 2
 5         
 6         for i in 0..<count {
 7             sum -= nums[i]
 8         }
 9         return sum
10     }
11 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!