0006 旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾榨汤，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。
例如: 數(shù)組 {3,4,5,1,2} 為 {1,2,3,4,5} 的一個(gè)旋轉(zhuǎn)趾娃，該數(shù)組的最小值為1。
說(shuō)明：給出的所有元素都大于0缔御，若數(shù)組大小為0茫舶，請(qǐng)返回0。
題目地址
解題報(bào)告
直接查找
本題解由微信公眾號(hào)
小猿刷題提供, 錯(cuò)誤之處, 歡迎指正.
在兩段范圍內(nèi)都是非降序刹淌，當(dāng)不符合這個(gè)規(guī)律時(shí)，就找到了最小數(shù)字
import java.util.*;
/**
* 微信公眾號(hào)"小猿刷題"
*/
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){
return 0;
}
int min = array[0];
for(int i = 1; i < array.length ; i ++ ){
if(array[i] < min){
min = array[i];
}
}
return min;
}
}
先排序再找
本題解由微信公眾號(hào)
小猿刷題提供, 錯(cuò)誤之處, 歡迎指正.
利用 Arrays 工具類里的排序函數(shù)讥耗，默認(rèn)的排序規(guī)則是從小到大有勾，排序后的數(shù)組第一個(gè)值就是最小值.
import java.util.*;
/**
* 微信公眾號(hào)"小猿刷題"
*/
public class Solution {
public int minNumberInRotateArray(int [] array) {
int n = array.length;
if(n == 0){
return 0;
}
Arrays.sort(array);
return array[0];
}
}
優(yōu)先級(jí)隊(duì)列
本題解由微信公眾號(hào)
小猿刷題提供, 錯(cuò)誤之處, 歡迎指正.
將數(shù)組元素挨著丟進(jìn)優(yōu)先隊(duì)列，優(yōu)先隊(duì)列默認(rèn)為最小堆古程，彈出的第一個(gè)數(shù)就是整個(gè)數(shù)組的最小值.
import java.util.*;
/**
* 微信公眾號(hào)"小猿刷題"
*/
public class Solution {
public int minNumberInRotateArray(int [] array) {
int n = array.length;
if(n == 0){
return 0;
}
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i = 0;i<n;i++){
queue.add(array[i]);
}
return queue.poll();
}
}
二分查找
本題解由微信公眾號(hào)
小猿刷題提供, 錯(cuò)誤之處, 歡迎指正.
二分查找變種蔼卡，沒(méi)有具體的值用來(lái)比較。那么用中間值和高低位進(jìn)行比較挣磨，看處于遞增還是遞減序列雇逞，進(jìn)行操作縮小范圍荤懂。
/**
* 微信公眾號(hào)"小猿刷題"
*/
public class Solution {
public int minNumberInRotateArray(int[] array) {
int i = 0;
int j = array.length - 1;
while (i < j) {
if (array[i] < array[j]) {
return array[i];
}
int mid = (i + j) / 2;
if (array[mid] > array[i]) {
i = mid + 1;
} else if (array[mid] < array[j]) {
j = mid; // 證明進(jìn)入了有序數(shù)組，直接輸出
} else {
i++;
}
}
return array[i];
}
}
