|
| 1 | +divde & conquer |
| 2 | +https://leetcode.com/problems/majority-element/discuss/51712/Python-different-solutions-(dictionary-bit-manipulation-sorting-divide-and-conquer-brute-force-etc). |
| 3 | +# two pass + dictionary |
| 4 | +def majorityElement1(self, nums): |
| 5 | + dic = {} |
| 6 | + for num in nums: |
| 7 | + dic[num] = dic.get(num, 0) + 1 |
| 8 | + for num in nums: |
| 9 | + if dic[num] > len(nums)//2: |
| 10 | + return num |
| 11 | + |
| 12 | +# one pass + dictionary |
| 13 | +def majorityElement2(self, nums): |
| 14 | + dic = {} |
| 15 | + for num in nums: |
| 16 | + if num not in dic: |
| 17 | + dic[num] = 1 |
| 18 | + if dic[num] > len(nums)//2: |
| 19 | + return num |
| 20 | + else: |
| 21 | + dic[num] += 1 |
| 22 | + |
| 23 | +# TLE |
| 24 | +def majorityElement3(self, nums): |
| 25 | + for i in xrange(len(nums)): |
| 26 | + count = 0 |
| 27 | + for j in xrange(len(nums)): |
| 28 | + if nums[j] == nums[i]: |
| 29 | + count += 1 |
| 30 | + if count > len(nums)//2: |
| 31 | + return nums[i] |
| 32 | + |
| 33 | +# Sotring |
| 34 | +def majorityElement4(self, nums): |
| 35 | + nums.sort() |
| 36 | + return nums[len(nums)//2] |
| 37 | + |
| 38 | +# Bit manipulation |
| 39 | +def majorityElement5(self, nums): |
| 40 | + bit = [0]*32 |
| 41 | + for num in nums: |
| 42 | + for j in xrange(32): |
| 43 | + bit[j] += num >> j & 1 |
| 44 | + res = 0 |
| 45 | + for i, val in enumerate(bit): |
| 46 | + if val > len(nums)//2: |
| 47 | + # if the 31th bit if 1, |
| 48 | + # it means it's a negative number |
| 49 | + if i == 31: |
| 50 | + res = -((1<<31)-res) |
| 51 | + else: |
| 52 | + res |= 1 << i |
| 53 | + return res |
| 54 | + |
| 55 | +# Divide and Conquer |
| 56 | +def majorityElement6(self, nums): |
| 57 | + if not nums: |
| 58 | + return None |
| 59 | + if len(nums) == 1: |
| 60 | + return nums[0] |
| 61 | + a = self.majorityElement(nums[:len(nums)//2]) |
| 62 | + b = self.majorityElement(nums[len(nums)//2:]) |
| 63 | + if a == b: |
| 64 | + return a |
| 65 | + return [b, a][nums.count(a) > len(nums)//2] |
| 66 | + |
| 67 | +# the idea here is if a pair of elements from the |
| 68 | +# list is not the same, then delete both, the last |
| 69 | +# remaining element is the majority number |
| 70 | +def majorityElement(self, nums): |
| 71 | + count, cand = 0, 0 |
| 72 | + for num in nums: |
| 73 | + if num == cand: |
| 74 | + count += 1 |
| 75 | + elif count == 0: |
| 76 | + cand, count = num, 1 |
| 77 | + else: |
| 78 | + count -= 1 |
| 79 | + return cand |