計算數組中符號變化的次數

1.概述

在本教程中，我們將學習兩種計算數組中符號變化次數的方法。首先，我們將介紹一個簡單的迭代演算法，該演算法遍歷數組，並在遇到符號變化時遞增計數器。

然後，我們將利用 Java 8 Streams 以簡潔的函數式風格實現相同的結果。在此過程中，我們將討論一些邊緣情況，例如零值。最後，我們將理解問題所在，並掌握實現高效易讀解決方案的策略。

2. 迭代方法

讓我們從一個簡單的循環開始，檢查每對連續元素並計算它們的符號何時不同。

為了一致地說明每種方法，我們使用以下數組作為範例：

int[] sampleArray = {1, -2, -3, 4, 0, -1, 5};

讓我們實作一個遍歷數組的方法。我們的方法將每個元素的符號與前一個非零符號進行比較。然後，當檢測到變化時，它會增加一個計數器：

int countSignChanges(int[] arr) {

 if (arr == null || arr.length < 2) {

 return 0;

 }

 int count = 0;



 int prevSign = Integer.signum(arr[0]);



 for (int i = 1; i < arr.length; i++) {

 int currentSign = Integer.signum(arr[i]);



 if (currentSign != 0 && prevSign != 0 && currentSign != prevSign) {

 count++;

 }



 if (currentSign != 0) {

 prevSign = currentSign;

 }

 }



 return count;

 }

此方法使用Integer.signum()將值規範化為 -1、0 或 1，以便直接比較符號。此方法會跳過零值，以避免將其計為符號變更。最後，只有當遇到非零值時，它才會更新先前的符號。

此演算法運行時間為線性時間O(n) ，其中n是數組中元素的數量。它佔用的空間為常數時間O(1) ，因此非常高效，適用於中等規模的資料集。

讓我們看看該方法應用於範例數組時的行為：

@Test

 void givenArray_whenExistsSignChanges_thenReturnSignChangesQuantity() {

 int result = countSignChanges(sampleArray);

 Assertions.assertThat(result).isEqualTo(4);

 }

此範例展示了一次完整的方法呼叫。它根據樣本數組中的符號變化驗證預期結果。計數僅反映有效的符號變化，忽略迭代過程中的零值。

3.使用Java 8 Streams

統計符號變化本身就是一個迭代任務。然而，我們可以使用流來表達相同的邏輯。這涉及將每個元素與其前一個元素配對，並根據符號差異進行過濾。

首先，讓我們實作一個使用流來計算符號變化次數的方法：

int countSignChangesStream(int[] arr) {

 if (arr == null || arr.length < 2) {

 return 0;

 }



 int[] signs = Arrays.stream(arr)

 .map(Integer::signum)

 .filter(s -> s != 0)

 .toArray();



 return (int) IntStream.range(1, signs.length)

 .filter(i -> signs[i] != signs[i - 1])

 .count();

 }

雖然這種方法更具聲明性和簡潔性，但它會創建中間數組和流。它的時間複雜度仍然是O(n) ，但與命令式版本相比，記憶體佔用增加。

讓我們針對範例數組測試基於流的方法：

@Test

 void givenArray_whenUsingStreams_thenReturnSignChangesQuantity() {

 int result = countSignChangesStream(sampleArray);

 Assertions.assertThat(result).isEqualTo(4);

 }

這次執行證實了基於功能流的方法產生與命令式方法相同的結果。

4. 結論

在本文中，我們探討了兩種解決數組符號變化計數問題的實用方法。迭代方法使用簡單的控制結構，提供了一個清晰且有效率的解決方案。它避免了不必要的記憶體分配，在效能和資源受限的情況下非常理想。

另一方面，Java 8 的 Streams 方法提供了更具表達力和聲明性的替代方案。它使熟悉函數式程式設計的人更容易理解其邏輯。然而，由於中間資料結構的存在，它會帶來額外的開銷。

兩種解決方案的時間複雜度均為O(n) ，但在記憶體佔用和實作風格上有所不同。選擇哪種方案取決於具體情況，清晰度、效能還是遵循現代 Java 實務才是首要考慮因素。

與往常一樣，原始碼可在 GitHub 上取得。