[Swift]LeetCode260.只出现一次的数字III|SingleNumberIII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10227202.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

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

注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

76ms

 1 class Solution {
 2     func singleNumber(_ nums: [Int]) -> [Int] {
 3 
 4         var res = [0, 0]
 5         var diff = nums.reduce(0){$0 ^ $1}
 6         diff &= -diff
 7         for num in nums {
 8             if num & diff != 0 {
 9                 res[0] ^= num
10             }
11             else {
12                 res[1] ^= num
13             }
14         }
15         return res
16     }
17 }

76ms

 1 class Solution {
 2     func singleNumber(_ nums: [Int]) -> [Int] {
 3         guard nums.count > 1 else {
 4             return nums
 5         }
 6         
 7         var result = nums[0]
 8         for num in nums[1...] {
 9             result ^= num
10         }
11         
12         var num1 = 0, num2 = 0, tmp = 1
13         while (result & tmp) == 0 {
14             tmp <<= 1
15         }
16         
17         for num in nums {
18             if (num & tmp) > 0 {
19                 num1 ^= num
20             }
21             else {
22                 num2 ^= num
23             }
24         }
25         
26         return [num1, num2]
27     }
28 }

80ms

 1 class Solution {
 2     func singleNumber(_ nums: [Int]) -> [Int] {
 3         var s: Set<Int> = Set(minimumCapacity: nums.count)
 4         for i in nums {
 5             if s.contains(i) {
 6                 s.remove(i)
 7             } else {
 8                 s.insert(i)
 9             }
10         }
11         return Array(s)
12     }
13 }

84ms

 1 class Solution {
 2     func singleNumber(_ nums: [Int]) -> [Int] {
 3         var array = nums.sorted()
 4         // print(array)
 5         var output:[Int] = []
 6         
 7         var i = 0
 8         while i < array.count {
 9             if i == array.count - 1 || array[i] != array[i+1] {
10                 output.append(array[i])
11             } else {
12                 i += 1
13             }
14             i += 1
15             if output.count > 1 {
16                 break
17             }
18         }
19         
20         return output
21     }
22 }

84ms

 1 class Solution {
 2     func singleNumber(_ nums: [Int]) -> [Int] {
 3         var result = [Int]()
 4         var temp = nums.sorted()
 5         for i in 0..<temp.count {
 6             if i == 0 {
 7                 if temp[i] != temp[i+1] {
 8                     result.append(temp[i])
 9                 }
10             } else if i == temp.count - 1{
11                 if temp[i] != temp[i-1] {
12                     result.append(temp[i])
13                 }
14             }
15             else {
16                 if temp[i] != temp[i-1] && temp[i] != temp[i+1]{
17                     result.append(temp[i])
18                 }
19             }
20         }
21         return result
22     }
23 }