[剑指Offer] Day 23: Mathematics

Authored by Tony Feng

Created on May 4th, 2022

Last Modified on May 29th, 2022

Task 1 - Q39. 数组中出现次数超过一半的数字

Question

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

Solution 1

1
2
3
4
5
6
7


class Solution: # Sort and Find the Medium
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None

        m = len(nums) // 2 
        return sorted(nums)[m]

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution: # Dictionary
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None

        dict = {}
        halfSize = len(nums) // 2
        for num in nums:
            if num in dict:
                dict[num] += 1
            else:
                dict[num] = 1

            if dict[num] > halfSize:
                    return num

Solution 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution: # Boyer–Moore majority vote algorithm
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None

        votes = 0
        ans = None
        for num in nums:
            if votes == 0:
                ans = num

            if num != ans:
                votes -= 1
            else:
                votes += 1
        
        return ans

Explanation

Solution 1
- Time Complexity: O(N * log(N))
- Space Complexity: O(1)
Solution 2
- Time Complexity: O(N)
- Space Complexity: O(N)
Solution 3
- Time Complexity: O(N)
- Space Complexity: O(1)
- Boyer–Moore majority vote algorithm
  - If n is majority, vote + 1; else vote - 1. Finally, vote must be positive.
  - If vote of the first $a$ numbers is 0, then the rest of vote is still positive, which means the majority number doesn’t change.

Task 2 - Q66. 构建乘积数组

Question

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。要求不能使用除法。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution: # Left-Right Traversal
    def constructArr(self, a: List[int]) -> List[int]:
        ans = [1] * len(a)

        # Travese from the left
        tmp = 1
        for i in range(0,len(a)):  
            ans[i] *= tmp
            tmp *= a[i]

        # Travese from the right
        tmp = 1
        for j in range(len(a)-1, -1, -1):
            ans[j] *= tmp
            tmp *= a[j]

        return ans

Explanation

Time Complexity: O(N)
Space Complexity: O(1), i.e. ans is a return variable so it won’t take into account.


B[0] =	1	A[1]	A[2]	…	A[n-2]	A[n-1]
B[1] =	A[0]	1	0	…	A[n-2]	A[n-1]
B[2] =	A[0]	A[1]	A[2]	…	A[n-2]	A[n-1]
…	…	…	…	…	…	…
B[n-2] =	A[0]	A[1]	A[2]	…	1	A[n-1]
B(n-1) =	A[0]	A[1]	A[2]	…	A[n-2]	1