資料結構
網路
關係資料庫管理系統 (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 次瀏覽
