資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Java程式查詢陣列中差值最大的兩個元素
在這個問題中，我們將使用Java查詢陣列中差值最大的兩個元素。
我們可以為每個元素建立一個組合，並找出每對元素之間的差值。之後，我們可以選擇差值最大的那對元素。另一種方法是排序陣列，然後取陣列中最大和最小的元素。
問題陳述
我們得到一個包含整數值的陣列。我們需要找到兩個陣列元素，以使它們之間的差值最大化。
輸入1
array[] = { 50, 10, 30, 400, 600, 200, 70, 90, 80, 322 }
輸出1
The maximum difference between 600 and 10 is 590.
輸入2
array[] = {1000, 30, 5000, 476, 987, 312 }
輸出2
The maximum difference is between 30 and 5000.
輸入3
array[] = {-70, -150, 40, 500, -90 }
輸出3
The smallest element in the array is -150, and the largest element is 500.
不同的方法
以下是查詢陣列中兩個元素的不同方法
使用蠻力法
在這種方法中，我們將建立包含兩個陣列元素的組合。之後，我們將計算這兩個元素的差值，並在需要時更新最大差值。
-
將‘curr_diff’初始化為0，以儲存兩個元素之間的差值，並將‘max_diff’初始化為第一個和第二個元素的差值。此外，初始化‘first’和‘second’變數以儲存差值最大的元素對。
-
從第0個索引開始遍歷陣列。此外，使用巢狀迴圈從p + 1索引遍歷陣列。
-
計算位於pth和qth索引處的陣列元素的絕對差值，並將它們儲存到curr_diff中。
-
如果curr_diff大於max_diff，則更新max_diff、first和second變數的值。
-
列印最大差值、first和second變數的值。
示例
import java.io.*;
public class Main {
public static void getMaxDiff(int array[], int arr_len) {
// Variable initialization
int curr_diff, max_diff = array[1] - array[0];
int first = array[1], second = array[0];
// Traverse the array and find the difference between each 2 elements
for (int p = 0; p < arr_len; p++) {
for (int q = p + 1; q < arr_len; q++) {
curr_diff = Math.abs(array[p] - array[q]);
// If the difference between two elements is greater than max_diff, update max_diff.
if (curr_diff > max_diff) {
max_diff = curr_diff;
first = array[p];
second = array[q];
}
}
}
System.out.println("Maximum difference is " + max_diff + " between " + first + " and " + second);
}
public static void main(String[] args) {
int array[] = { 50, 10, 30, 400, 600, 200, 70, 90, 80, 322 };
int arr_len = array.length;
getMaxDiff(array, arr_len);
}
}
輸出
Maximum difference is 590 between 10 and 600
時間複雜度：O(N^2)，用於建立每個元素的組合。
空間複雜度：O(1)，因為我們不使用任何動態空間。
使用排序
在這種方法中，我們將對陣列進行排序。之後，我們可以取排序後陣列的第一個和最後一個元素，以獲得任意兩個陣列元素之間的最大差值。
- 首先匯入java.io和java.util包的必要類。
- 使用Arrays.sort()方法對陣列進行排序。
- 計算nums[arr_len - 1]和nums[0]之間的差值。
- 在輸出中列印差值、nums[arr_len - 1]和nums[0]。
示例
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
int nums[] = { 50, 10, 30, 400, 600, 200, 70, 90, 80, 322 };
int arr_len = nums.length;
// sort array
Arrays.sort(nums);
// Get the max difference
int max_diff = nums[arr_len - 1] - nums[0];
// print max difference
System.out.println("Maximum difference is " + max_diff + " between " +nums[0] + " and " + nums[arr_len - 1] );
}
}
輸出
Maximum difference is 590 between 10 and 600
時間複雜度：O(NlogN)，用於對陣列進行排序。
空間複雜度：O(N)，用於對陣列進行排序。
使用最佳化方法
在這種方法中，我們將遍歷陣列以查詢給定陣列中的最大和最小元素。之後，我們可以計算最小和最大元素的差值，這將是最大差值。
-
將maxi和mini初始化為第一個陣列元素，以儲存最大和最小元素。
-
開始迭代陣列。
-
如果當前陣列元素超過maxi，則更新maxi。如果當前元素小於mini，則更新mini。
-
計算maxi和mini之間的差值。
-
列印maxi和mini之間的差值，以顯示在輸出中。
示例
import java.io.*;
public class Main {
public static void getMaxDiff(int array[], int arr_len) {
int maxi = array[0];
int mini = array[0];
// Finding the maximum and minimum element in the array
for (int p = 0; p < arr_len; p++) {
if (array[p] > maxi) {
maxi = array[p];
}
if (array[p] < mini) {
mini = array[p];
}
}
// Getting the maximum difference
int max_diff = maxi - mini;
System.out.println("Maximum difference is " + max_diff + " between " + mini + " and " + maxi);
}
public static void main(String[] args) {
int array[] = { -70, -150, 40, 500, -90 };
int arr_len = array.length;
getMaxDiff(array, arr_len);
}
}
輸出
Maximum difference is 650 between -150 and 500
時間複雜度：O(N)，用於遍歷陣列。
空間複雜度：O(1)，因為我們不使用額外的空間。
我們已經看到了三種查詢差值最大的兩個元素的方法。只有當我們計算最小和最大陣列元素的差值時，才能獲得兩個陣列元素之間的最大差值。就時間和空間複雜度而言，第三種方法提供了最最佳化的解決方案。
415 次檢視
