Java旋轉數(shù)組中最小數(shù)字具體實現(xiàn)(圖文詳解版)

更新時間：2023年08月15日 08:39:23 作者：楠枬

這篇文章主要給大家介紹了關于Java旋轉數(shù)組中最小數(shù)字具體實現(xiàn)的相關資料,旋轉數(shù)組,說明數(shù)據(jù)不變,只是改變位置,文中通過代碼示例介紹的非常詳細,需要的朋友可以參考下

1.題目描述

有一個長度為 n 的非降序數(shù)組，比如[1,2,3,4,5]，將它進行旋轉，即把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，變成一個旋轉數(shù)組，比如變成了[3,4,5,1,2]，或者[4,5,1,2,3]這樣的。請問，給定這樣一個旋轉數(shù)組，求數(shù)組中的最小值。

示例

輸入：[3, 4, 5, 1, 2]

返回值：1

2.題解

分析

題目中的數(shù)組為

題目要求我們找出其中的最小值

具體實現(xiàn)

方法一（遍歷）：

尋找數(shù)組中的最小值，遍歷數(shù)組即可找到最小值

public class Solution {
    public int minNumberInRotateArray(int[] nums) {
        if(nums.length == 0){
            return -1;
        }
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (min > nums[i]) {
                min = nums[i];
            }
        }
        return min;
    }
}

方法二（排序）：

使用Arrays.sort方法對數(shù)組進行降序排序，則nums[0]即為數(shù)組的最小值

import java.util.Arrays;
public class Solution {
    public int minNumberInRotateArray (int[] nums) {
        if(nums.length == 0){
            return -1;
        }
        Arrays.sort(nums);
        return nums[0];
    }
}

方法三（二分查找）：

數(shù)組原本是一個升序數(shù)組，旋轉之后，數(shù)組被分成兩部分，前、后半部分分別為升序，后半部分小于前半部分，我們可以利用二分查找的思想，找到其旋轉點，即可找到數(shù)組的最小值

首先找到數(shù)組首尾兩端元素，并求出數(shù)組中間的下標

再將數(shù)組中間值與數(shù)組首尾兩端元素進行比較，

若nums[mid] > nums[right]，則left = mid + 1

若nums[mid] < nums[right]，則right = mid

若nums[mid] = nums[right]，則將right向左移動一位，即right--

然后進入下一次循環(huán)，循環(huán)的條件為left < right

通過不斷縮小范圍，最終能夠找到數(shù)組的最小值

完整代碼

public class Solution {
    public int minNumberInRotateArray(int[] nums) {
        if(nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            //找到數(shù)組的中點
            int mid = (left + right) / 2;
            if(nums[mid] > nums[right]){
                //旋轉點在[mid+1, j]中，跳過mid+1左邊元素
                left = mid + 1;
            } else if(nums[mid] < nums[right]){
                //旋轉點在[left, mid]中，跳過mid右邊元素
                right = mid;
            }else{
                //縮小right繼續(xù)查找
                right--;
            }
        }
        //返回旋轉點
        return nums[left];
    }
}

注：題目出自?？途W，鏈接如下

旋轉數(shù)組的最小數(shù)字_?？皖}霸_?？途W (nowcoder.com)