Java技術Web開發高級語言其他技術腳本語言數據庫大數據教程XML技術專業教育框架軟件工具教程通信技術微軟技術軟件測試手機開發前端技術人工智能實例代碼

尋找列表的峰值元素

瀏覽人數：159最近更新：

    一、簡介

    數組中的峰值元素對於許多演算法都很重要，可以提供對資料集特徵的寶貴見解。在本教程中，我們將探討峰元素的概念，解釋其重要性並探索在單峰和多峰場景中識別它們的有效方法。

    2.什麼是峰值元素？

    數組中的峰值元素定義為嚴格大於其相鄰元素的元素。如果邊緣元素大於其唯一的相鄰元素，則認為它們處於峰值位置。

    在元素相等的情況下，不存在嚴格的峰值。相反，峰值是元素超過其鄰居的第一個實例。

    2.1.例子

    為了更好地理解峰值元素的概念，請看以下範例：

    範例1：

    List: [1, 2, 20, 3, 1, 0]
 Peak Element: 20

    這裡，20 是一個峰值，因為它大於其相鄰元素。

    範例2：

    List: [5, 13, 15, 25, 40, 75, 100]
 Peak Element: 100

    100 是一個峰值，因為它大於 75 且其右側沒有元素。

    範例3：

    List: [9, 30, 13, 2, 23, 104, 67, 12]
 Peak Element: 30 or 104, as both are valid peaks

    30 和 104 都符合峰值。

    3. 尋找單峰元素

    當陣列僅包含一個峰值元素時，簡單的方法是利用線性搜尋。此演算法掃描數組元素，將每個元素與其相鄰元素進行比較，直到找到峰值。此方法的時間複雜度為O(n) ，其中 n 是陣列的大小。

    public class SinglePeakFinder {
 public static OptionalInt findSinglePeak(int[] arr) {
 int n = arr.length;

 if (n < 2) {
 return n == 0 ? OptionalInt.empty() : OptionalInt.of(arr[0]);
 }

 if (arr[0] >= arr[1]) {
 return OptionalInt.of(arr[0]);
 }

 for (int i = 1; i < n - 1; i++) {
 if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) {
 return OptionalInt.of(arr[i]);
 }
 }

 if (arr[n - 1] >= arr[n - 2]) {
 return OptionalInt.of(arr[n - 1]);
 }

 return OptionalInt.empty();
 }
 }

    演算法從索引 1 到 n-2 迭代數組，檢查當前元素是否大於其鄰居。如果找到峰值，則傳回包含該峰值的OptionalInt。此外，此演算法還處理峰值位於數組極值的邊緣情況。

    public class SinglePeakFinderUnitTest {
 @Test
 void findSinglePeak_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeak() {
 int[] arr = {0, 10, 2, 4, 5, 1};
 OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
 assertTrue(peak.isPresent());
 assertEquals(10, peak.getAsInt());
 }

 @Test
 void findSinglePeak_givenEmptyArray_thenReturnsEmptyOptional() {
 int[] arr = {};
 OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
 assertTrue(peak.isEmpty());
 }

 @Test
 void findSinglePeak_givenEqualElementArray_thenReturnsCorrectPeak() {
 int[] arr = {-2, -2, -2, -2, -2};
 OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
 assertTrue(peak.isPresent());
 assertEquals(-2, peak.getAsInt());
 }
 }

    對於雙調數組（其特徵是單調遞增序列隨後是單調遞減序列），可以更有效地找到峰值。透過應用改進的二分搜尋技術，我們可以在O(log n)時間內找到峰值，從而顯著降低複雜性。

    需要注意的是，確定數組是否為雙調的需要進行檢查，在最壞的情況下，可能會接近線性時間。因此，當陣列的雙調性質已知時，二分搜尋方法的效率增益最有影響力。

    4. 尋找多個峰元素

    識別數組中的多個峰值元素通常需要檢查每個元素與其相鄰元素的關係，從而產生時間複雜度為O(n)的線性搜尋演算法。這種方法確保不會忽略任何潛在峰值，使其適用於一般陣列。

    在特定場景中，當陣列結構允許分割成可預測的模式時，可以應用修改的二分搜尋技術來更有效地找到峰值。讓我們使用修改後的二分搜尋演算法來實現O(log n)的時間複雜度。

    演算法說明：

    • 初始化指標：從兩個指標開始， low和high ，代表陣列的範圍。
    • 二分查找：計算目前範圍的mid索引。
    • 將 Mid 與鄰居進行比較：檢查索引mid處的元素是否大於其鄰居。
      • 如果true ， mid為峰值。
      • 如果為false ，則向具有更大鄰居的一側移動，確保我們向潛在的峰值移動。
    • 重複：繼續此過程，直到範圍縮小為單一元素。
    public class MultiplePeakFinder {
 public static List<Integer> findPeaks(int[] arr) {
 List<Integer> peaks = new ArrayList<>();

 if (arr == null || arr.length == 0) {
 return peaks;
 }
 findPeakElements(arr, 0, arr.length - 1, peaks, arr.length);
 return peaks;
 }

 private static void findPeakElements(int[] arr, int low, int high, List<Integer> peaks, int length) {
 if (low > high) {
 return;
 }

 int mid = low + (high - low) / 2;

 boolean isPeak = (mid == 0 || arr[mid] > arr[mid - 1]) && (mid == length - 1 || arr[mid] > arr[mid + 1]);
 boolean isFirstInSequence = mid > 0 && arr[mid] == arr[mid - 1] && arr[mid] > arr[mid + 1];

 if (isPeak || isFirstInSequence) {

 if (!peaks.contains(arr[mid])) {
 peaks.add(arr[mid]);
 }
 }

 findPeakElements(arr, low, mid - 1, peaks, length);
 findPeakElements(arr, mid + 1, high, peaks, length);
 }
 }

    MultiplePeakFinder類別採用改進的二分搜尋演算法來有效識別數組中的多個峰元素。 findPeaks方法初始化兩個指標low和high ，表示陣列的範圍。

    它計算中間索引 ( mid ) 並檢查mid處的元素是否大於其鄰居。如果為true ，則它將mid標記為峰值，並繼續在潛在的峰值豐富區域中搜尋。

    public class MultiplePeakFinderUnitTest {
 @Test
 void findPeaks_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeaks() {

 MultiplePeakFinder finder = new MultiplePeakFinder();
 int[] array = {1, 13, 7, 0, 4, 1, 4, 45, 50};
 List<Integer> peaks = finder.findPeaks(array);

 assertEquals(3, peaks.size());
 assertTrue(peaks.contains(4));
 assertTrue(peaks.contains(13));
 assertTrue(peaks.contains(50));
 }
 }

    二分搜尋查找峰值的效率取決於數組的結構，允許在不檢查每個元素的情況下進行峰值檢測。然而，在不知道數組的結構或缺乏合適的二分搜尋模式的情況下，線性搜尋是最可靠的方法，保證不會忽略任何峰值。

    5. 處理邊緣情況

    理解和解決邊緣情況對於確保峰元演算法的穩健性和可靠性至關重要。

    5.1.無峰陣列

    在陣列不包含峰元素的情況下，必須指出這種不存在。當沒有找到峰值時，我們會傳回一個空數組：

    public class PeakElementFinder {
 public List<Integer> findPeakElements(int[] arr) {
 int n = arr.length;
 List<Integer> peaks = new ArrayList<>();

 if (n == 0) {
 return peaks;
 }

 for (int i = 0; i < n; i++) {
 if (isPeak(arr, i, n)) {
 peaks.add(arr[i]);
 }
 }

 return peaks;
 }

 private boolean isPeak(int[] arr, int index, int n) {
 return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
 }
 }

    findPeakElement方法迭代數組，利用isPeak輔助函數來辨識峰值。如果未找到峰值，則傳回一個空數組。

    public class PeakElementFinderUnitTest {
 @Test
 void findPeakElement_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeak() {
 PeakElementFinder finder = new PeakElementFinder();
 int[] array = {1, 2, 3, 2, 1};
 List<Integer> peaks = finder.findPeakElements(array);
 assertEquals(1, peaks.size());
 assertTrue(peaks.contains(3));
 }

 @Test
 void findPeakElement_givenArrayOfIntegers_whenNoPeaks_thenReturnsEmptyList() {
 PeakElementFinder finder = new PeakElementFinder();
 int[] array = {};
 List<Integer> peaks = finder.findPeakElements(array);
 assertEquals(0, peaks.size());
 }
 }

    5.2.極值處具有峰值的陣列

    當第一個或最後一個元素存在峰值時，需要特別考慮以避免未定義的鄰居比較。讓我們在isPeak方法中加入條件檢查來處理這些情況：

    private boolean isPeak(int[] arr, int index, int n) {
 if (index == 0) {
 return n > 1 ? arr[index] >= arr[index + 1] : true;
 } else if (index == n - 1) {
 return arr[index] >= arr[index - 1];
 }

 return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
 }

    此修改可確保正確識別極端處的峰值，而無需嘗試與未定義的鄰居進行比較。

    public class PeakElementFinderUnitTest {
 @Test
 void findPeakElement_givenArrayOfIntegers_whenPeaksAtExtremes_thenReturnsCorrectPeak() {
 PeakElementFinder finder = new PeakElementFinder();
 int[] array = {5, 2, 1, 3, 4};
 List<Integer> peaks = finder.findPeakElements(array);
 assertEquals(2, peaks.size());
 assertTrue(peaks.contains(5));
 assertTrue(peaks.contains(4));
 }
 }

    5.3.處理高原（連續相等元素）

    在陣列包含連續相等元素的情況下，傳回第一次出現的索引至關重要。 isPeak函數透過跳過連續的相等元素來處理此問題：

    private boolean isPeak(int[] arr, int index, int n) {
 if (index == 0) {
 return n > 1 ? arr[index] >= arr[index + 1] : true;
 } else if (index == n - 1) {
 return arr[index] >= arr[index - 1];
 } else if (arr[index] == arr[index + 1] && arr[index] > arr[index - 1]) {
 int i = index;

 while (i < n - 1 && arr[i] == arr[i + 1]) {
 i++;
 }
 return i == n - 1 || arr[i] > arr[i + 1];
 } else {
 return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
 }
 }

    findPeakElement函數會跳過連續的相等元素，確保在辨識峰值時會傳回第一次出現的索引。

    public class PeakElementFinderUnitTest {
 @Test
 void findPeakElement_givenArrayOfIntegers_whenPlateaus_thenReturnsCorrectPeak() {
 PeakElementFinder finder = new PeakElementFinder();
 int[] array = {1, 2, 2, 2, 3, 4, 5};
 List<Integer> peaks = finder.findPeakElements(array);
 assertEquals(1, peaks.size());
 assertTrue(peaks.contains(5));
 }
 }

    六，結論

    了解尋找峰值元素的技術使開發人員能夠在設計高效且有彈性的演算法時做出明智的決策。發現峰值元素的方法有多種，這些方法提供不同的時間複雜度，例如 O(log n) 或 O(n)。

    這些方法的選擇取決於特定要求和應用限制。選擇正確的演算法與應用程式要實現的效率和效能目標一致。

    您可以在 GitHub 上找到所有程式碼範例。

    本作品係原創或者翻譯，採用《署名-非商業性使用-禁止演繹4.0國際》許可協議

    最新文章

    Java 周刊，第 538 期尋找給定年份的復活節星期日的日期MongoRepository 中使用 Limit 和 Skip 的不同方式在 Java 中尋找 URL 的重定向 URL重寫 toString() 方法時列印預設值求最長對稱子串的長度給定 URL 從 S3 下載文件Java 中的迭代器與 forEach()探索 Java 中的複數算術運算Gson 的多態性