LeetCode 153 在有序旋轉數組中找最小-1

MkkHou 發布于2019-08-14 16:59 / 661人閱讀

摘要：難度就是說一個從小到大排序好的數組循環移位不知多少次，求最小值。數組無重復值無重復的話就比較簡單，用二分查找即可。當前游標始終是左右游標中點位置，與左右游標的數值比較。解法有幾個要點基本終止條件為左邊的數比當前的數大，那么當前數即是最小值。

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

就是說一個從小到大排序好的數組循環移位不知多少次，求最小值。數組無重復值！
無重復的話就比較簡單，用二分查找即可。算法時間復雜度為O(log n)。
基本想法就是定義三個游標：左游標，右游標，當前游標。當前游標始終是左右游標中點位置，與左右游標的數值比較。

解法有幾個要點：

基本終止條件為：左邊的數比當前的數大，那么當前數即是最小值。

額外終止條件：當左右游標重合，或者左右游標相鄰。

需要考慮邊界條件。

移動條件1：如果當前游標的數值比左游標數值小，則游標左移。

移動條件2：如果當前游標的數值比右游標數值大，則游標右移。

默認移動：游標左移。

我寫的算法代碼和測試代碼如下：

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));
    }
}

云服務器 GPU云服務器 153郵箱旋轉數組二維數組旋轉數組最小值

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66356.html

LeetCode 154 在有序旋轉數組中找最小-2

摘要：難度就是說一個從小到大排序好的數組循環移位不知多少次，求最小值。比如全部是的數列，和除了某位置有個，其余全部是的數列，都是合法的。在這里，測試用例也進行了增加，盡量覆蓋各種奇葩情況。 Follow up for Find Minimum in Rotated Sorted Array:What if duplicates are allowed?Would this affect th...

evin2016 2019-08-14 17:02 評論0 收藏0
70道前端LeetCode題目集合及視頻講解（持續更新中...）

前端LeetCode刷題下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關注。數組類 26 刪除排序數組中的重復項 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數組中的重復項2 88 合并兩個有序數組 167 兩數之和II - 輸入有序數組 118 楊輝三角 169 easy 求眾數 1...

mayaohua 2019-08-26 10:46 評論0 收藏0
6-9月技術文章匯總

摘要：分布式的管理和當我在談論架構時我在談啥狀態碼詳解無狀態協議和請求支持哪些方法分層協議棧有哪些數據結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統設計工程在線診斷系統設計與實現索引背后的數據結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
leetcode153-154 find minimum rotated sorted array

摘要：題目要求假設有一個升序排序的數組，在某個節點處斷開并調換了順序。尋找這個斷開數組中的最小元素。但是如果我們將頭尾的重復元素清楚，而只是在數組中間存在重復元素的話，如，這樣并不會影響升序數組位置的判斷。題目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor...

DrizzleX 2019-08-16 10:42 評論0 收藏0
[Leetcode] Search in Rotated Sorted Array 搜索旋轉有序數組

摘要：如果左邊的點比右邊的大，說明這兩個點之間有一個旋轉點，導致了不再有序。因為只有一個旋轉點，所以一分為二后，肯定有一半是有序的。 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...

thursday 2019-08-14 12:38 評論0 收藏0