数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在已排序数组中查找出现次数超过 N/2 的数字（Java）
在 Java 中，我们可能需要确定某个特定数字在一个已排序数组中出现的次数是否超过总数的一半。本文探讨了有效解决此问题的不同方法。我们将讨论语法并为每种方法提供详细解释。最后，您将清楚地掌握如何使用 Java 识别在一个已排序数组中出现次数超过 N/2 的数字。
语法
让我们首先检查本文中描述的算法使用的语法：
public class Main {
public static int findMajorityElement(int[] nums) {
// Your code here
}
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。
在 main 方法中，我们初始化一个名为 nums 的已排序数组。
我们调用 findMajorityElement 方法，传递 nums 作为参数，并将结果存储在 majorityElement 变量中。
最后，如果找到众数元素，我们使用 System.out.println() 打印它。
方法 1
算法
将变量 count 初始化为 1，并将 majorityElement 初始化为 nums[0]。
从列表 1 开始，遍历整个数组。
如果当前元素等于 majorityElement，则将 count 加 1；否则，将 count 减 1。如果 count 变为 0，则将当前元素赋值给 majorityElement 并将 count 设置为 1。
最后，返回 majorityElement 作为结果。
示例
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，并将 majorityElement 初始化为数组的第一个元素。然后，它从第二个元素开始迭代数组。对于每个元素，它检查它是否等于 majorityElement。如果是，则递增 count；否则，则递减 count。此方法利用了众数元素出现的次数将超过 N/2 的事实。
如果 count 变为 0，则意味着前一个元素不再是众数元素的候选者。在这种情况下，我们将 majorityElement 更新为当前元素并将 count 重置为 1。在迭代结束时，我们返回 majorityElement 作为结果。
方法 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
算法
将变量 candidate 初始化为 nums[0]，并将 count 初始化为 1。
从索引 1 迭代到 nums.length - 1。
如果当前元素等于 candidate，则将 count 加 1。
如果当前元素与 candidate 不同，则将 count 减 1。
如果 count 变为 0，则将 candidate 更新为当前元素并将 count 设置为 1。
迭代结束后，再次遍历数组并计算 candidate 的出现次数。
如果计数大于 nums.length / 2，则返回 candidate 作为众数元素；否则，返回 -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 项目中成功解决此问题的能力。
269 次浏览
