在 Java 中查找排序数组中出现次数超过 N/2 次的数字
在 Java 中，有时我们需要确定特定数字是否在排序数组中出现超过一半的时间。本文探讨了有效解决此问题的不同方法。我们将讨论语法并为每种方法提供详细解释。通过总结，您将清楚地掌握如何使用 Java 识别排序数组中出现次数超过 N/2 次的数字。
语法
让我们首先检查本文所述算法所采用的语法 -
public class Main {
public static int findMajorityElement(int[] nums) {
// 此处为您的代码
}
public static void main(String[] args) {
int[] nums = { /* Initialize your sorted array here */ };
int majorityElement = findMajorityElement(nums);
System.out.println("Majority Element: " + majorityElement);
}
}
语法说明
我们定义一个名为 Main 的公共类。
在 Main 类中，我们声明一个公共静态方法 findMajorityElement，该方法以整数数组 nums 为参数。如果存在多数元素，此方法将返回该元素；否则，它将返回 -1。
在主方法中，我们初始化一个名为 nums 的排序数组。
我们调用 findMajorityElement 方法，将 nums 作为参数传递，并将结果存储在 majorElement 变量中。
最后，如果找到多数元素，我们使用 System.out.println() 打印它。
方法 1
算法
将变量 count 初始化为 1，将 majorElement 初始化为 nums[0]。
从列表 1 开始，并强调整个展览。
假设正在进行的组件与 majorElement 匹配，则将计数增加一；无论如何，将计数减少一。如果 count 变为 0，则将当前元素指定为 majorElement，并将 count 设置为 1。
最后，返回 majorElement 作为结果。
示例
public class Main {
public static int findMajorityElement(int[] nums) {
int count = 1;
int majorityElement = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] == majorityElement)
count++;
else
count--;
if (count == 0) {
majorityElement = nums[i];
count = 1;
}
}
return majorityElement;
}
public static void main(String[] args) {
int[] nums = {2, 2, 2, 3, 4, 2, 2}; // Example array initialization
int majorityElement = findMajorityElement(nums);
System.out.println("Majority Element: " + majorityElement);
}
}
输出
Majority Element: 2
方法 1 中的代码说明
代码首先将 count 初始化为 1，将 majorElement 初始化为数组的第一个元素。然后，它从第二个元素开始遍历数组。对于每个元素，它检查它是否等于 majorElement。如果是，则增加 count；否则，减少 count。此方法利用了多数元素将出现超过 N/2 次的事实。
如果 count 变为 0，则表示前一个元素不再是多数元素的候选者。在这种情况下，我们将 majorElement 更新为当前元素，并将 count 重置为 1。在迭代结束时，我们将 majorElement 作为结果返回。
方法 2
算法
将变量 midIndex 初始化为 nums.length / 2。
从索引 0 到 midIndex - 1 遍历数组。
检查当前索引处的元素是否等于索引 midIndex 处的元素。
如果元素相等，则返回构成多数的元素。
如果数组的前半部分不包含多数条目，则返回 -1。
示例
public class Main {
public static int findMajorityElement(int[] nums) {
int midIndex = nums.length / 2;
for (int i = 0; i < midIndex; i++) {
if (nums[i] == nums[midIndex])
return nums[i];
}
return -1;
}
public static void main(String[] args) {
int[] nums = { /* Initialize your sorted array here */ };
int majorityElement = findMajorityElement(nums);
System.out.println("Majority Element: " + majorityElement);
}
}
输出
Majority Element: -1
方法 2 的代码说明
在此方法中，数组被分成两个相等的部分，并将前半部分的每个成员与中间元素 (nums[midIndex]) 进行比较。如果找到匹配项，则返回该元素作为多数元素。如果前半部分没有匹配项，则返回 -1，表示没有多数元素。
方法 3
算法
从索引 0 到 nums.length - 1 遍历数组。
检查当前索引处的元素是否等于索引 nums.length / 2 处的元素。
将变量 count 初始化为 0。
如果元素相等，则将 count 增加 1。
如果 count 大于 nums.length / 2，则返回该元素作为多数元素。
如果未找到多数元素，则返回 -1。
示例
public class Main {
public static int findMajorityElement(int[] nums) {
int midIndex = nums.length / 2;
int majorityElement = nums[midIndex];
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == majorityElement)
count++;
if (count > midIndex)
return majorityElement;
}
return -1;
}
public static void main(String[] args) {
int[] nums = {2, 2, 2, 3, 4, 2, 2}; // Example array initialization
int majorityElement = findMajorityElement(nums);
System.out.println("Majority Element: " + majorityElement);
}
}
输出
Majority Element: -1
方法 3 中的代码说明
在此方法中，我们遍历整个数组并跟踪 nums.length / 2 处元素的计数。如果计数超过 nums.length / 2，我们将该元素作为多数元素返回。如果没有找到多数元素，则返回 -1。
方法 4
算法
将变量候选初始化为 nums[0]，并将计数设为 1。
从索引 1 到 nums.length - 1 遍历数组。
如果当前元素等于候选，则将计数增加 1。
如果当前元素与候选不同，则将计数减少 1。
如果计数变为 0，则将候选更新为当前元素，并将计数设置为 1。
迭代后，再次遍历数组并计算候选的出现次数。
如果计数大于 nums.length / 2，返回候选元素作为多数元素；否则返回 -1。
示例
public class Main {
public static int findMajorityElement(int[] nums) {
int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == candidate)
count++;
else
count--;
if (count == 0) {
candidate = nums[i];
count = 1;
}
}
count = 0;
for (int num : nums) {
if (num == candidate)
count++;
}
if (count > nums.length / 2)
return candidate;
else
return -1;
}
public static void main(String[] args) {
int[] nums = {2, 2, 2, 3, 4, 2, 2}; // Example array initialization
int majorityElement = findMajorityElement(nums);
System.out.println("Majority Element: " + majorityElement);
}
}
输出
Majority Element: 2
方法 4 中的代码说明
此方法遵循 Boyer-Moore 投票算法。每次迭代数组时，都会保留一个候选元素，计数为 1。每次遇到新元素时，计数都会减少。如果计数为零，则选择新的候选元素。迭代后，我们再次迭代数组以计算候选元素的出现次数。如果计数超过 nums.length / 2，我们将候选元素作为多数元素返回；否则，我们返回 -1。
结论
在本文中，我们探索了使用 Java 在排序数组中查找数字出现次数超过 N/2 次的四种不同方法。每种策略都提供了具有不同程度有效性的特殊解决方案。现在，通过理解算法、查看现成的代码并注意分步说明，您已经掌握了在 Java 项目中成功解决此问题的技能。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/
