剑指offer-28、数组中出现次数超过⼀半的数字
<h2 id="题描述">题⽬描述</h2><p>数组中有⼀个数字出现的次数超过数组⻓度的⼀半，请找出这个数字。例如输⼊⼀个⻓度为 9 的数组 {1,2,3,2,2,2,5,4,2} 。由于数字 2 在数组中出现了 5 次，超过数组⻓度的⼀半，因此输出 2 。如果不存在则输出 0 。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="哈希表法hashmap">哈希表法（HashMap）</h3>
<p>哈希表法通过统计每个数字的出现次数来解决问题。遍历数组时，使用哈希表记录每个数字出现的次数，一旦发现某个数字的出现次数超过数组长度的一半，立即返回该数字。</p>
<pre><code class="language-java">public class Solution {
public int MoreThanHalfNum(int[] nums) {
// 创建哈希表，key为数字，value为出现次数
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
// 获取当前数字的出现次数并加1，若不存在则初始化为0再加1
int count = map.getOrDefault(num, 0) + 1;
// 若当前数字出现次数已超过数组长度一半，则返回该数字
if (count > nums.length / 2) {
return num;
}
map.put(num, count); // 更新哈希表
}
return 0; // 如果不存在多数元素，返回0（但题目假设总是存在）
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，其中 n 是数组的长度。我们只需遍历数组一次。</li>
<li><strong>空间复杂度</strong>：O(n)，最坏情况下需要存储所有不同的数字。</li>
</ul>
<h3 id="排序法">排序法</h3>
<p>排序法的思路非常巧妙：由于<strong>多数元素的数量超过数组长度的一半</strong>，那么将数组排序后，中间位置的元素一定是多数元素。</p>
<pre><code class="language-java">public class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums); // 对数组进行排序
return nums; // 返回中间位置的元素
}
}
</code></pre>
<h3 id="摩尔投票法boyer-moore-voting-algorithm">摩尔投票法（Boyer-Moore Voting Algorithm）</h3>
<ol>
<li>如果使⽤ hashmap 直接统计，需要额外的空间，我们不希望使⽤额外空间;</li>
<li>如果使⽤排序之后再统计，需要时间复杂度为O(nlogn)， 我们希望时间复杂度更低⼀点。</li>
</ol>
<p>摩尔投票法是一种高效且空间复杂度低的算法。其核心思想是<strong>通过票数的抵消来找出多数元素</strong>。算法维护一个候选众数 <code>candidate</code> 和其票数 <code>count</code>。遍历数组时，若 <code>count</code> 为0，则选择当前数字作为候选；若当前数字与候选相同，则票数加1，否则减1。由于多数元素的存在，最终剩下的候选一定是多数元素。</p>
<pre><code class="language-java">public class Solution {
public int majorityElement(int[] nums) {
int candidate = 0; // 候选众数
int count = 0; // 票数统计
for (int num : nums) {
if (count == 0) { // 如果票数为0，选择当前数字作为候选
candidate = num;
}
// 如果当前数字与候选相同，则票数加1，否则减1
count += (num == candidate) ? 1 : -1;
}
// 可选：验证candidate是否真的是多数元素（根据题目假设，通常不需要）
// 但如果题目要求不存在多数元素时返回0，则需要验证步骤
count = 0;
for (int num : nums) {
if (num == candidate) count++;
}
return count > nums.length / 2 ? candidate : 0;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，只需遍历数组两次（一次投票，一次验证）。</li>
<li><strong>空间复杂度</strong>：O(1)，只使用了常数个额外变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19076699
頁:
[1]