在 Java 中查找數組的中間元素

一、簡介

在本教程中，我們將探討查找數組中間元素的問題。數組是一種存儲相同類型數據元素的數據結構。

數組的元素以連續的方式存儲在內存中，並與索引相關聯。該數組具有固定長度。

2. 問題陳述

給定一個包含n元素的數組，我們應該返回一個包含該數組中間元素的新數組。如果輸入數組的長度為奇數，則該數組有一個中間元素。另一方面，如果輸入數組的長度為偶數，則數組有兩個中間元素。

我們代碼的輸出應該返回一個長度為 1 或 2 的數組，具體取決於輸入數組。

讓我們看一些例子：

• 給定一個包含 5 個元素的輸入數組：[1, 2, 3, 4, 5]，輸出為 [3]。由於數組的長度是 5，這是一個奇數，我們可以說存在一個中間元素，在我們的例子中是 3。
• 給定一個包含 6 個元素的輸入數組：[1, 2, 3, 4, 5, 6]，輸出為 [3, 4]。本例中數組的長度為 6，是偶數。這裡，3和4都是數組的中間元素。

我們還應該考慮我們問題的一些邊緣情況。對於空輸入數組，沒有中間元素，因此空數組是正確的輸出。數組本身是長度為 1 和 2 的數組的輸出。

3. 使用數組運算的中間元素

數組的長度告訴我們它包含的元素數量。長度為n的數組將包含n元素。可以使用從 0 開始的索引來訪問元素。

3.1.奇數長度數組的中間元素

給定一個長度為n的數組，其中n是奇數，我們可以說該數組的第一個索引始終為0,而該數組的最後一個索引為n-1 。長度為 99 的數組具有從 0 到 98 的索引，其中索引 49 是中間索引。

**我們知道兩個值a和b,之間的中點始終為 ( a + b) / 2.**在我們的例子中，考慮a = 0和b = n = 98 ，我們可以發現中間索引為(0 + 99) / 2 = 49 。因此，訪問n/2元素將為我們提供所需的輸出：

int[] middleOfArray(int[] array) {
 int n = array.length;
 int mid = n / 2;
 return new int[] { array[mid] };
 }

需要注意的是， n始終是整數，因為它告訴我們數組的長度，並且長度不能是小數。因此，當我們執行n/2時，Java 將執行整數除法並丟棄小數部分。因此，在前面的 99 個元素的示例中，中間元素將為 99/2 = 49，而不是 49.5 或 50。

3.2.偶數長度數組的中間元素

現在我們知道如何找到奇數長度數組的中間元素，讓我們將解決方案擴展到偶數長度數組。

偶數長度的數組沒有定義的單個中間元素。長度為 100 且元素從索引 0 開始的數組的中間元素將位於索引 49和 50處。因此，長度為n的數組（其中n為偶數）的中間元素是索引 ( n/2)-1和**n/2** .由於我們的輸出取決於輸入數組的長度，因此讓我們將它們組合成一個方法：

int[] middleOfArray(int[] array) {
 if (ObjectUtils.isEmpty(array) || array.length < 3) {
 return array;<br /> }
 int n = array.length;
 int mid = n / 2;
 if (n % 2 == 0) {
 int mid2 = mid - 1;
 return new int[] { array[mid2], array[mid] };
 } else {
 return new int[] { array[mid] };
 }
 }

我們還添加一個小測試來驗證我們的解決方案是否適用於所有類型的數組：

int[] array = new int[100];
 for (int i = 0; i < array.length; i++) {
 array[i] = i + 1;
 }
 int[] expectedMidArray = { 50, 51 };
 MiddleOfArray middleOfArray = new MiddleOfArray();
 Assert.assertArrayEquals(expectedMidArray, middleOfArray.middleOfArray(array));

 int[] expectedMidArrayForOddLength = { 50 };
 Assert.assertArrayEquals(expectedMidArrayForOddLength, middleOfArray.middleOfArray(Arrays.copyOfRange(array, 0, 99)));

3.3.兩點之間數組的中間元素

在前面的部分中，我們將數組的整個長度視為輸入，併計算了整個數組的中間部分。可能需要計算由開始和結束索引給出的數組的一部分或子集的中間元素。

我們不能再使用n的值（數組的長度）來計算中點。我們可以按原樣使用提供的值並找到中間點： middle = (start + end) / 2 ，而不是像之前那樣替換start = 0和end = n 。

int[] middleOfArrayWithStartEnd(int[] array, int start, int end) {
 int mid = (start + end) / 2;
 int n = end - start;
 if (n % 2 == 0) {
 int mid2 = mid - 1;
 return new int[] { array[mid2], array[mid] };
 } else {
 return new int[] { array[mid] };
 }
 }

然而，這種方法有一個主要缺點。

考慮一下我們正在處理一個非常大的數組（按Integer.MAX_VALUE順序）。 Integer.MAX_VALUE值是 2147483647。我們需要找到索引 100 和 2147483647 之間的數組的中間元素。

因此，在我們的示例中， start = 100且end = Integer.MAX_VALUE.當我們應用公式查找中點時， start + end為 4294966747。該值大於Integer.MAX_VALUE ，從而導致溢出。當我們在 Java 中運行它時，我們得到 -2147483549，這證實了溢出。

解決這個問題相當簡單。我們首先找到start和end,然後將(end – start) / 2添加到start.所以， **mid = start + (end – start) / 2** .這總是可以讓我們免於溢出：

int[] middleOfArrayWithStartEnd(int[] array, int start, int end) {
 int mid = start + (end - start) / 2;
 int n = end - start;
 if (n % 2 == 0) {
 int mid2 = mid - 1;
 return new int[] { array[mid2], array[mid] };
 } else {
 return new int[] { array[mid] };
 }
 }

3.4.查找中間元素的數組運算的性能

我們知道訪問數組中的元素是一個 O(1) 的操作。由於數組元素放置在內存中的連續塊中，因此跳轉到特定索引是一個恆定時間操作。因此，我們可以說上述所有操作都是常數時間 O(1) 操作。

4. 使用按位運算的中間元素

我們可以使用按位運算作為查找數組中間元素的替代方法。位運算是對輸入值的二進制數字（位）進行操作。按位運算符有很多類別，例如按位邏輯運算符和按位移位運算符。

這裡我們將使用一種特定類型的移位運算符，稱為無符號右移位運算符，即>>>。

顧名思義，無符號右移運算符將輸入值的所有位向右移動，並且新創建的空白空間用 0 填充。這有助於斷言輸出始終為正。

無符號移位運算符通常用於將數字除以 2 的冪。因此， a >>> n相當於a / (2 ^ n) 。我們利用這個事實來查找開始和結束之間的中間元素：

int[] middleOfArrayWithStartEndBitwise(int[] array, int start, int end) {
 int mid = (start + end) >>> 1;
 int n = end - start;
 if (n % 2 == 0) {
 int mid2 = mid - 1;
 return new int[] { array[mid2], array[mid] };
 } else {
 return new int[] { array[mid] };
 }
 }

諸如此類的按位運算速度更快，因為它們是在硬件中的較低級別實現的，現代 CPU 可以利用它。

5. 數組的中位數

在我們的討論中，我們沒有討論元素的性質或其順序。如果數組中的元素都是數字且本質上已排序，則會出現一種特殊情況。

排序數據集的中間元素稱為數據集的中值，在數學和統計學中非常重要。**中值是對任何數據集的集中趨勢的度量，並提供對數據集的典型值可能是什麼的見解。**

對於偶數長度的數組，中位數通常是通過查找兩個中間元素的平均值來計算的：

int medianOfArray(int[] array, int start, int end) {
 Arrays.sort(array); // for safety. This can be ignored
 int mid = (start + end) >>> 1;
 int n = end - start;
 if (n % 2 == 0) {
 int mid2 = mid - 1;
 return (array[mid2] + array[mid]) / 2;
 } else {
 return array[mid];
 }
 }

中值期望數據集按正確的排序順序排列。因此，如果我們不確定數組的性質，我們應該首先按升序或降序對數組進行排序，然後使用前面的任何方法找到中間值。

考慮一個問題陳述，我們需要找到一個國家的房價中位數。考慮到問題的性質，我們可以假設輸入數據太大，無法容納傳統計算機的可用內存。如果 JVM 無法一次將整個數組加載到內存中，則很難應用上述方法來查找中位數。

在數據集太大而無法放入內存的情況下，我們可以考慮將輸入放在流中而不是傳統的數組中。然後，我們可以使用其他數據結構（例如具有流數據的堆）找到數據流的中位數。

六，結論

在本文中，我們研究了查找數組中間元素的幾種方法。我們還討論了這個解決方案如何幫助我們找到數組的中位數。

與往常一樣，所有代碼示例都可以在 GitHub 上找到.