136. 只出现一次的数字 Single Number
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
代码1： 用哈希表计数
package main import "fmt" func singleNumber(nums []int) int { hash := make(map[int]int) for _, num := range nums { hash[num]++ } for num, count := range hash { if count == 1 { return num } } return 0 } func main() { nums := []int{2, 2, 1} fmt.Println(singleNumber(nums)) nums = []int{4, 1, 2, 1, 2} fmt.Println(singleNumber(nums)) }
代码2：异或运算
package main import "fmt" func singleNumber(nums []int) int { res := 0 for _, num := range nums { res ^= num } return res } func main() { nums := []int{2, 2, 1} fmt.Println(singleNumber(nums)) nums = []int{4, 1, 2, 1, 2} fmt.Println(singleNumber(nums)) }
代码3： 算术运算
package main import "fmt" func singleNumber(nums []int) int { hash := make(map[int]int) sum1, sum2 := 0, 0 for _, num := range nums { hash[num]++ sum1 += num } for num, _ := range hash { sum2 += 2 * num } return sum2 - sum1 } func main() { nums := []int{2, 2, 1} fmt.Println(singleNumber(nums)) nums = []int{4, 1, 2, 1, 2} fmt.Println(singleNumber(nums)) }
输出：
1
4
137. 只出现一次的数字 II Single Number II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99
提示：
1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
代码1： 用哈希表计数
package main import "fmt" func singleNumber(nums []int) int { hash := make(map[int]int) for _, num := range nums { hash[num]++ } for num, count := range hash { if count == 1 { return num } } return 0 } func main() { nums := []int{2, 2, 3, 2} fmt.Println(singleNumber(nums)) nums = []int{0, 1, 0, 1, 0, 1, 99} fmt.Println(singleNumber(nums)) }
代码2： 位运算
package main import "fmt" func singleNumber(nums []int) int { res := 0 for i := 0; i < 64; i++ { sum := 0 for _, num := range nums { sum += (num >> i) & 1 } if sum%3 != 0 { res |= 1 << i } } return res } func main() { nums := []int{2, 2, 3, 2} fmt.Println(singleNumber(nums)) nums = []int{0, 1, 0, 1, 0, 1, 99} fmt.Println(singleNumber(nums)) }
代码3： 算术运算
package main import "fmt" func singleNumber(nums []int) int { hash := make(map[int]int) sum1, sum2 := 0, 0 for _, num := range nums { hash[num]++ sum1 += num } for num, _ := range hash { sum2 += 3 * num } return (sum2 - sum1) / 2 } func main() { nums := []int{2, 2, 3, 2} fmt.Println(singleNumber(nums)) nums = []int{0, 1, 0, 1, 0, 1, 99} fmt.Println(singleNumber(nums)) }
输出：
3
99
260. 只出现一次的数字 III Single Number III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例 1：
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0]
输出：[-1,0]
示例 3：
输入：nums = [0,1]
输出：[1,0]
提示：
2 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次
代码1： 用哈希表计数
package main import "fmt" func singleNumber(nums []int) []int { m := make(map[int]int) for _, num := range nums { m[num]++ } res := make([]int, 0, 2) for num, count := range m { if count == 1 { res = append(res, num) } } return res } func main() { nums := []int{1, 2, 1, 3, 2, 5} fmt.Println(singleNumber(nums)) nums = []int{-1, 0} fmt.Println(singleNumber(nums)) nums = []int{0, 1} fmt.Println(singleNumber(nums)) }
代码2： 位运算分组异或
package main import "fmt" func singleNumber(nums []int) []int { xor := 0 for _, num := range nums { xor ^= num } mask := 1 for (xor & mask) == 0 { mask <<= 1 } a, b := 0, 0 for _, num := range nums { if num&mask != 0 { a ^= num } else { b ^= num } } return []int{a, b} } func main() { nums := []int{1, 2, 1, 3, 2, 5} fmt.Println(singleNumber(nums)) nums = []int{-1, 0} fmt.Println(singleNumber(nums)) nums = []int{0, 1} fmt.Println(singleNumber(nums)) }
