資訊專欄INFORMATION COLUMN
摘要：難度就是說一個(gè)從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。數(shù)組無(wú)重復(fù)值無(wú)重復(fù)的話就比較簡(jiǎn)單，用二分查找即可。當(dāng)前游標(biāo)始終是左右游標(biāo)中點(diǎn)位置，與左右游標(biāo)的數(shù)值比較。解法有幾個(gè)要點(diǎn)基本終止條件為左邊的數(shù)比當(dāng)前的數(shù)大，那么當(dāng)前數(shù)即是最小值。
Question:
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
難度: medium
就是說一個(gè)從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。數(shù)組無(wú)重復(fù)值！
無(wú)重復(fù)的話就比較簡(jiǎn)單，用二分查找即可。算法時(shí)間復(fù)雜度為O(log n)。
基本想法就是定義三個(gè)游標(biāo)：左游標(biāo)，右游標(biāo)，當(dāng)前游標(biāo)。當(dāng)前游標(biāo)始終是左右游標(biāo)中點(diǎn)位置，與左右游標(biāo)的數(shù)值比較。
解法有幾個(gè)要點(diǎn)：
基本終止條件為：左邊的數(shù)比當(dāng)前的數(shù)大，那么當(dāng)前數(shù)即是最小值。
額外終止條件：當(dāng)左右游標(biāo)重合，或者左右游標(biāo)相鄰。
需要考慮邊界條件。
移動(dòng)條件1：如果當(dāng)前游標(biāo)的數(shù)值比左游標(biāo)數(shù)值小，則游標(biāo)左移。
移動(dòng)條件2：如果當(dāng)前游標(biāo)的數(shù)值比右游標(biāo)數(shù)值大，則游標(biāo)右移。
默認(rèn)移動(dòng)：游標(biāo)左移。
我寫的算法代碼和測(cè)試代碼如下：
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class ShiftFinder {
public static int findMin(int[] array) {
if (array.length == 0) {
return 0;
}
if (array.length == 1) {
return array[0];
}
int len = array.length;
int l = 0;
int r = len - 1;
int cur = (l + r) / 2;
while (true) {
if (array[cur] < array[index(cur - 1, len)]) {
break;
}
if (l == r) {
cur = l;
break;
}
if (r == (l + 1)) {
if (array[l] < array[r]) {
cur = l;
} else {
cur = r;
}
break;
}
if (array[cur] < array[l]) {
r = cur;
cur = (l + r) / 2;
continue;
}
if (array[cur] > array[r]) {
l = cur;
cur = (l + r) / 2;
continue;
}
r = cur;
cur = (l + r) / 2;
}
return array[cur];
}
public static int index(int cur, int length) {
return (cur % length + length) % length;
}
public static void main(String[] args) {
int[] a = { 7, 8, 11, 12, 13, 14, 19, 22, 1, 2, 4, 5 };
int[] b = { 1, 2, 3, 4, 5, 6, 7 };
int[] c = { 11, 1, 2, 4, 5, 7, 8 };
int[] d = { 1 };
int[] e = { 1, 2 };
int[] f = { 2, 1 };
int[] g = { 3, 1, 2 };
// System.out.println(ShiftFinder.index(0, 10));
// System.out.println(ShiftFinder.index(2, 10));
// System.out.println(ShiftFinder.index(-2, 10));
// System.out.println(ShiftFinder.index(13, 10));
// System.out.println(ShiftFinder.index(-13, 10));
// System.out.println(ShiftFinder.index(1, 1));
System.out.println(ShiftFinder.findMin(a));
System.out.println(ShiftFinder.findMin(b));
System.out.println(ShiftFinder.findMin(c));
System.out.println(ShiftFinder.findMin(d));
System.out.println(ShiftFinder.findMin(e));
System.out.println(ShiftFinder.findMin(f));
System.out.println(ShiftFinder.findMin(g));
// gen random shift array
int attemptSize = 100;
int randomRange = 999;
Random rdm = new Random();
Set ts = new TreeSet();
for (int i = 0; i < attemptSize; i++) {
ts.add(rdm.nextInt(randomRange));
}
int shift = rdm.nextInt(ts.size());
System.out.println("size: " + ts.size() + "; shift: " + shift);
Integer[] iay = new Integer[ts.size()];
ts.toArray(iay);
int[] aa = new int[ts.size()];
for (int i = 0; i < ts.size(); i++) {
aa[ShiftFinder.index(i + shift, aa.length)] = iay[i];
}
for (int i = 0; i < aa.length; i++) {
System.out.print(aa[i] + " ");
}
System.out.println();
System.out.println("random minimum find: " + ShiftFinder.findMin(aa));
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66356.html
摘要：難度就是說一個(gè)從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。比如全部是的數(shù)列，和除了某位置有個(gè)，其余全部是的數(shù)列，都是合法的。在這里，測(cè)試用例也進(jìn)行了增加，盡量覆蓋各種奇葩情況。 Follow up for Find Minimum in Rotated Sorted Array:What if duplicates are allowed?Would this affect th...
前端LeetCode刷題 下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關(guān)注。 數(shù)組類 26 刪除排序數(shù)組中的重復(fù)項(xiàng) 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數(shù)組中的重復(fù)項(xiàng)2 88 合并兩個(gè)有序數(shù)組 167 兩數(shù)之和II - 輸入有序數(shù)組 118 楊輝三角 169 easy 求眾數(shù) 1...
摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無(wú)狀態(tài)協(xié)議和請(qǐng)求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場(chǎng)景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...
摘要：題目要求假設(shè)有一個(gè)升序排序的數(shù)組，在某個(gè)節(jié)點(diǎn)處斷開并調(diào)換了順序。尋找這個(gè)斷開數(shù)組中的最小元素。但是如果我們將頭尾的重復(fù)元素清楚，而只是在數(shù)組中間存在重復(fù)元素的話，如，這樣并不會(huì)影響升序數(shù)組位置的判斷。 題目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor...
摘要：如果左邊的點(diǎn)比右邊的大，說明這兩個(gè)點(diǎn)之間有一個(gè)旋轉(zhuǎn)點(diǎn)，導(dǎo)致了不再有序。因?yàn)橹挥幸粋€(gè)旋轉(zhuǎn)點(diǎn)，所以一分為二后，肯定有一半是有序的。 Search in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 mi...
閱讀 3340·2021-11-22 14:44
閱讀 2550·2019-08-30 14:10
閱讀 2610·2019-08-30 13:12
閱讀 1227·2019-08-29 18:36
閱讀 1352·2019-08-29 16:16
閱讀 3340·2019-08-26 10:33
閱讀 1770·2019-08-23 18:16
閱讀 389·2019-08-23 18:12
