-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsingle_number.py
143 lines (126 loc) · 4.45 KB
/
single_number.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
# https://leetcode.com/problems/single-number/
# 136. Single Number
# Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
# You must implement a solution with a linear runtime complexity and use only constant extra space.
# Example 1:
# Input: nums = [2,2,1]
# Output: 1
# Example 2:
# Input: nums = [4,1,2,1,2]
# Output: 4
# Example 3:
# Input: nums = [1]
# Output: 1
# Constraints:
# 1 <= nums.length <= 3 * 104
# -3 * 104 <= nums[i] <= 3 * 104
# Each element in the array appears twice except for one element which appears only once.
#######################
# https://leetcode.com/problems/single-number-ii/description/
# 137. Single Number II
# Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
# You must implement a solution with a linear runtime complexity and use only constant extra space.
# Example 1:
# Input: nums = [2,2,3,2]
# Output: 3
# Example 2:
# Input: nums = [0,1,0,1,0,1,99]
# Output: 99
# Constraints:
# 1 <= nums.length <= 3 * 104
# -231 <= nums[i] <= 231 - 1
# Each element in nums appears exactly three times except for one element which appears once.
# https://docs-python.ru/standart-library/modul-functools-python/funktsija-reduce-modulja-functools/
from functools import reduce
from collections import Counter, defaultdict
from typing import List
class Solution:
def singleNumberIII(self, nums: List[int]) -> int:
''' Single Number (reduce)'''
return reduce(lambda acc, y: acc ^ y, nums)
def singleNumber(self, nums: List[int]) -> int:
''' Single Number (FOR-loop)'''
# return reduce(lambda x, y: x ^ y, nums)
for i in range(1, len(nums)):
# Проводим побитовую операцию xor
nums[0] ^= nums[i]
return nums[0]
def singleNumberII(self, nums: List[int]) -> int:
'''
Single Number II
Approach: Magic
Explanation
https://leetcode.com/problems/single-number-ii/solutions/3714928/bit-manipulation-c-java-python-beginner-friendly/
'''
ones = 0
twos = 0
for num in nums:
ones ^= (num & ~twos)
twos ^= (num & ~ones)
return ones
def singleNumberBF(self, nums: List[int]) -> int:
'''
Single Number II
Approach: Brute Force
'''
count = defaultdict(int)
for x in nums:
count[x] += 1
for x, freq in count.items():
if freq == 1:
return x
return 0
def singleNumberBFII(self, nums: List[int]) -> int:
'''
Single Number II
Approach: Brute Force with Counter
'''
count = Counter(nums)
for x, freq in count.items():
if freq == 1:
return x
return 0
if __name__ == "__main__":
print("Single Number (FOR-loop)")
print(Solution().singleNumber([2,2,1,1,1]))
# Output: 1
print(Solution().singleNumber([2,2,1]))
# Output: 1
print(Solution().singleNumber([4,1,2,1,2]))
# Output: 4
print(Solution().singleNumber([1]))
# Output: 1
print(Solution().singleNumber([0,1,0,1,0,1]))
# Output: 1 - couldn't resolve correctly
print(Solution().singleNumber([0,1,0,1]))
# Output: 0 - unexpected situation
print("Single Number (reduce)")
print(Solution().singleNumberIII([2,2,1,1,1]))
# Output: 1
print(Solution().singleNumberIII([2,2,1]))
# Output: 1
print(Solution().singleNumberIII([4,1,2,1,2]))
# Output: 4
print(Solution().singleNumberIII([1]))
# Output: 1
print(Solution().singleNumberIII([0,1,0,1,0,1]))
# Output: 1 - couldn't resolve correctly
print(Solution().singleNumberIII([0,1,0,1]))
# Output: 0 - unexpected situation
print("Single Number (Brute Force)")
print(Solution().singleNumberBF([0,1,0,1,0,1,99]))
# Output: 99
print(Solution().singleNumber([0,1,0,1,0,1,99]))
# Output: 98 - couldn't resolve correctly
print(Solution().singleNumberBF([0,1,0,1,0,1]))
# Output: 0 - unexpected situation
print("Single Number II")
print(Solution().singleNumberII([2,2,3,2]))
# Output: 3
print(Solution().singleNumberII([0,1,0,1,0,1,99]))
# Output: 99
print(Solution().singleNumberII([0,1,0,1,0,1]))
# Output: 0
print("Single Number II (Brute Force)")
print(Solution().singleNumberBFII([0,1,0,1,0,1,99]))
# Output: 99