2023-12-05

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

Boyer-Moore 投票算法之所以能够正确工作，是因为出现次数大于 n/2 的元素（多数元素）的存在性保证了算法的有效性。

算法的核心思想在于通过消除不同的元素对当前候选多数元素的影响，从而找到数组中的多数元素。

以下是算法的详细解释：

1. 初始化候选多数元素和计数器： 开始时将候选多数元素设为 None，计数器设为 0。

2. 遍历数组： 对于数组中的每个元素，

   • 如果计数器为 0，说明当前的候选多数元素不足以抵消前面的元素对多数元素的影响，因此将当前元素设为新的候选多数元素。
   • 如果当前元素与候选多数元素相同，增加计数器；否则减少计数器。这一步实际上是在模拟相互抵消的过程。

3. 最终得到的候选多数元素： 由于多数元素的出现次数大于 n/2，因此通过这样的投票过程，最终的候选多数元素即为数组的多数元素。

这是因为多数元素的出现次数大于其他所有元素的出现次数之和，所以即使其他元素与多数元素相互抵消，最终多数元素的计数仍然会保持正值。

这个算法的时间复杂度是 O(n)，因为它只对数组进行了一次线性遍历。空间复杂度是 O(1)，因为算法只使用了常数个额外的变量。

Copy
1func majorityElement(nums []int) int {
2    // 初始化候选多数元素和计数器
3    var candidate int
4    count := 0
5
6    // 遍历数组
7    for _, num := range nums {
8        // 如果计数器为0，将当前元素设为候选多数元素
9        if count == 0 {
10            candidate = num
11        }
12
13        // 如果当前元素与候选多数元素相同，增加计数器
14        // 否则减少计数器，模拟相互抵消的过程
15        if num == candidate {
16            count++
17        } else {
18            count--
19        }
20    }
21
22    return candidate
23}

‍

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

反转数组的操作实际上可以帮助我们实现循环移动数组的效果。让我们通过一个简单的例子来说明：

假设有数组 [1, 2, 3, 4, 5, 6, 7]​，并且我们希望将其向右循环移动3个位置。我们可以按照以下步骤来实现：

1. 整体反转数组： [7, 6, 5, 4, 3, 2, 1]​
2. 反转前k个元素： [5, 6, 7, 4, 3, 2, 1]​
3. 反转剩余的元素： [5, 6, 7, 1, 2, 3, 4]​

通过这三个步骤，我们实现了将数组向右循环移动3个位置的目标。

这种方法的关键在于通过反转操作，我们可以改变数组中元素的相对顺序。整体反转数组实际上将原数组的最后k个元素移动到了数组的前面，而反转前k个元素和反转剩余的元素操作则进一步调整了元素的顺序，最终得到了我们希望的结果。

这样的操作在时间复杂度上是比较高效的，只需要进行三次线性时间复杂度的遍历操作，而不需要额外的空间。

Copy
1func rotate(nums []int, k int) {
2   // 对k取余，避免多次循环移动时出现重复的移动
3   k %= len(nums)
4
5   // 第一次反转整个数组
6   reverse(nums, 0, len(nums)-1)
7
8   // 第二次反转前k个元素
9   reverse(nums, 0, k-1)
10
11   // 第三次反转剩余的元素
12   reverse(nums, k, len(nums)-1)
13}
14
15// 数组反转函数，将数组从start到end的元素反转
16func reverse(nums []int, start, end int) {
17   // 使用双指针，start指向数组起始位置，end指向数组结束位置
18   for start < end {
19       // 交换start和end位置的元素
20       nums[start], nums[end] = nums[end], nums[start]
21       // 移动指针，向数组中间靠拢
22       start++
23       end--
24   }
25}

‍

昨天写了四题，今天就写两题，摸了。