溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文章向大家介紹使用Java怎么查找旋轉數組中的最小數字的基本知識點總結和需要注意事項，具有一定的參考價值，需要的朋友可以參考一下。
Java是一門面向對象編程語言，可以編寫桌面應用程序、Web應用程序、分布式系統和嵌入式系統應用程序。
代碼實現如下：
public class Test08 {
public static int getTheMin(int nums[]) {
if (nums == null || nums.length == 0) {
throw new RuntimeException("input error!");
}
int result = nums[0];
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] < nums[i]) {
result = nums[i + 1];
break;
}
}
return result;
}
public static void main(String[] args) {
// 典型輸入，單調升序的數組的一個旋轉
int[] array1 = {3, 4, 5, 1, 2};
System.out.println(getTheMin(array1));
// 有重復數字，并且重復的數字剛好的最小的數字
int[] array2 = {3, 4, 5, 1, 1, 2};
System.out.println(getTheMin(array2));
// 有重復數字，但重復的數字不是第一個數字和最后一個數字
int[] array3 = {3, 4, 5, 1, 2, 2};
System.out.println(getTheMin(array3));
// 有重復的數字，并且重復的數字剛好是第一個數字和最后一個數字
int[] array4 = {1, 0, 1, 1, 1};
System.out.println(getTheMin(array4));
// 單調升序數組，旋轉0個元素，也就是單調升序數組本身
int[] array5 = {1, 2, 3, 4, 5};
System.out.println(getTheMin(array5));
// 數組中只有一個數字
int[] array6 = {2};
System.out.println(getTheMin(array6));
// 數組中數字都相同
int[] array7 = {1, 1, 1, 1, 1, 1, 1};
System.out.println(getTheMin(array7));
}
}打印結果沒什么毛病。不過這樣的方法顯然不是最優的，我們看看有沒有辦法找出更加優質的方法處理。
有序，還要查找？
找到這兩個關鍵字，我們不免會想到我們的二分查找法，但不少小伙伴肯定會問，我們這個數組旋轉后已經不是一個真正的有序數組了，不過倒像是兩個遞增的數組組合而成的，我們可以這樣思考。
我們可以設定兩個下標 low 和 high，并設定 mid = (low + high)/2，我們自然就可以找到數組中間的元素 array[mid]，如果中間的元素位于前面的遞增數組，那么它應該大于或者等于 low 下標對應的元素，此時數組中最小的元素應該位于該元素的后面，我們可以把 low 下標指向該中間元素，這樣可以縮小查找的范圍。
同樣，如果中間元素位于后面的遞增子數組，那么它應該小于或者等于 high 下標對應的元素。此時該數組中最小的元素應該位于該中間元素的前面。我們就可以把 high 下標更新到中位數的下標，這樣也可以縮小查找的范圍，移動之后的 high 下標對應的元素仍然在后面的遞增子數組中。
不管是更新 low 還是 high，我們的查找范圍都會縮小為原來的一半，接下來我們再用更新的下標去重復新一輪的查找。直到最后兩個下標相鄰，也就是我們的循環結束條件。
說了一堆，似乎已經繞的云里霧里了，我們不妨就拿題干中的這個輸入來模擬驗證一下我們的算法。
input：{3，4，5，1，2}
此時 low = 0，high = 4，mid = 2，對應的值分別是：num[low] = 3，num[high] = 2，num[mid] = 5
由于 num[mid] > num[low]，所以 num[mid] 應該是在左邊的遞增子數組中。
更新 low = mid = 2，num[low] = 5，mid = (low+high)/2 = 3，num[mid] = 1;
high - low ≠ 1 ，繼續更新
由于 num[mid] < num[high]，所以斷定 num[mid] = 1 位于右邊的自增子數組中；
更新 high = mid = 3，由于 high - mid = 1,所以結束循環，得到最小值 num[high] = 1;
我們再來看看 Java 中如何用代碼實現這個思路：
public class Test08 {
public static int getTheMin(int nums[]) {
if (nums == null || nums.length == 0) {
throw new RuntimeException("input error!");
}
// 如果只有一個元素，直接返回
if (nums.length == 1)
return nums[0];
int result = nums[0];
int low = 0, high = nums.length - 1;
int mid;
// 確保 low 下標對應的值在左邊的遞增子數組，high 對應的值在右邊遞增子數組
while (nums[low] >= nums[high]) {
// 確保循環結束條件
if (high - low == 1) {
return nums[high];
}
// 取中間位置
mid = (low + high) / 2;
// 代表中間元素在左邊遞增子數組
if (nums[mid] >= nums[low]) {
low = mid;
} else {
high = mid;
}
}
return result;
}
public static void main(String[] args) {
// 典型輸入，單調升序的數組的一個旋轉
int[] array1 = {3, 4, 5, 1, 2};
System.out.println(getTheMin(array1));
// 有重復數字，并且重復的數字剛好的最小的數字
int[] array2 = {3, 4, 5, 1, 1, 2};
System.out.println(getTheMin(array2));
// 有重復數字，但重復的數字不是第一個數字和最后一個數字
int[] array3 = {3, 4, 5, 1, 2, 2};
System.out.println(getTheMin(array3));
// 有重復的數字，并且重復的數字剛好是第一個數字和最后一個數字
int[] array4 = {1, 0, 1, 1, 1};
System.out.println(getTheMin(array4));
// 單調升序數組，旋轉0個元素，也就是單調升序數組本身
int[] array5 = {1, 2, 3, 4, 5};
System.out.println(getTheMin(array5));
// 數組中只有一個數字
int[] array6 = {2};
System.out.println(getTheMin(array6));
// 數組中數字都相同
int[] array7 = {1, 1, 1, 1, 1, 1, 1};
System.out.println(getTheMin(array7));
// 特殊的不知道如何移動
int[] array8 = {1, 0, 1, 1, 1};
System.out.println(getTheMin(array8));
}
}前面我們提到在旋轉數組中，由于是把遞增排序數組的前面的若干個數字搬到數組后面，因為第一個數字總是大于或者等于最后一個數字，而還有一種特殊情況是移動了 0 個元素，即數組本身，也是它自己的旋轉數組。這種情況本身數組就是有序的了，所以我們只需要返回第一個元素就好了，這也是為什么我先給 result 賦值為 nums[0] 的原因。
上述代碼就完美了嗎？我們通過測試用例并沒有達到我們的要求，我們具體看看 array8 這個輸入。先模擬計算機運行分析一下：
low = 0, high = 4, mid = 2, nums[low] = 1, nums[high] = 1,nums[mid] = 1;
由于 nums[mid] >= nums[low]，故認定 nums[mid] = 1 在左邊遞增子數組中；
所以更新 high = mid = 2,mid = (low+high)/2 = 1;
nums[low] = 1,nums[mid] = 1,nums[high] = 1;
high - low ≠ 1，繼續循環；
由于 nums[mid] >= nums[low]，故認定 nums[mid] = 1 在左邊遞增子數組中；
所以更新 high = mid = 1,由于 high - low = 1,故退出循環，得到 result = 1；
但我們一眼了然，明顯我們的最小值不是 1 ，而是 0 ，所以當 array[low]、array[mid]、array[high] 相等的時候，我們的程序并不知道應該如何移動，按照目前的移動方式就默認 array[mid] 在左邊遞增子數組了，這顯然是不負責任的做法。
我們修正一下代碼：
public class Test08 {
public static int getTheMin(int nums[]) {
if (nums == null || nums.length == 0) {
throw new RuntimeException("input error!");
}
// 如果只有一個元素，直接返回
if (nums.length == 1)
return nums[0];
int result = nums[0];
int low = 0, high = nums.length - 1;
int mid = low;
// 確保 low 下標對應的值在左邊的遞增子數組，high 對應的值在右邊遞增子數組
while (nums[low] >= nums[high]) {
// 確保循環結束條件
if (high - low == 1) {
return nums[high];
}
// 取中間位置
mid = (low + high) / 2;
// 三值相等的特殊情況，則需要從頭到尾查找最小的值
if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
return midInorder(nums, low, high);
}
// 代表中間元素在左邊遞增子數組
if (nums[mid] >= nums[low]) {
low = mid;
} else {
high = mid;
}
}
return result;
}
/**
* 查找數組中的最小值
*
* @param nums 數組
* @param start 數組開始位置
* @param end 數組結束位置
* @return 找到的最小的數字
*/
public static int midInorder(int[] nums, int start, int end) {
int result = nums[start];
for (int i = start + 1; i <= end; i++) {
if (result > nums[i])
result = nums[i];
}
return result;
}
public static void main(String[] args) {
// 典型輸入，單調升序的數組的一個旋轉
int[] array1 = {3, 4, 5, 1, 2};
System.out.println(getTheMin(array1));
// 有重復數字，并且重復的數字剛好的最小的數字
int[] array2 = {3, 4, 5, 1, 1, 2};
System.out.println(getTheMin(array2));
// 有重復數字，但重復的數字不是第一個數字和最后一個數字
int[] array3 = {3, 4, 5, 1, 2, 2};
System.out.println(getTheMin(array3));
// 有重復的數字，并且重復的數字剛好是第一個數字和最后一個數字
int[] array4 = {1, 0, 1, 1, 1};
System.out.println(getTheMin(array4));
// 單調升序數組，旋轉0個元素，也就是單調升序數組本身
int[] array5 = {1, 2, 3, 4, 5};
System.out.println(getTheMin(array5));
// 數組中只有一個數字
int[] array6 = {2};
System.out.println(getTheMin(array6));
// 數組中數字都相同
int[] array7 = {1, 1, 1, 1, 1, 1, 1};
System.out.println(getTheMin(array7));
// 特殊的不知道如何移動
int[] array8 = {1, 0, 1, 1, 1};
System.out.println(getTheMin(array8));
}
}以上就是小編為大家帶來的使用Java怎么查找旋轉數組中的最小數字的全部內容了，希望大家多多支持億速云！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
