国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode 154 在有序旋轉(zhuǎn)數(shù)組中找最小-2

evin2016 / 3357人閱讀

摘要:難度就是說一個從小到大排序好的數(shù)組循環(huán)移位不知多少次,求最小值。比如全部是的數(shù)列,和除了某位置有個,其余全部是的數(shù)列,都是合法的。在這里,測試用例也進(jìn)行了增加,盡量覆蓋各種奇葩情況。

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
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.
The array may contain duplicates.

難度: Hard

就是說一個從小到大排序好的數(shù)組循環(huán)移位不知多少次,求最小值。數(shù)組可以有重復(fù)值!
這就比無重復(fù)的難一些了。
可以重復(fù)會帶來不少問題,之前的不重復(fù)循環(huán)移位的判定條件都要重新思考是否有效。
比如全部是1的數(shù)列,和除了某位置有個2,其余全部是1的數(shù)列,都是合法的。
上個題目中的移動和終止條件似乎都無效了

相比上題而言,這里有幾個針對重復(fù)值的關(guān)鍵:

如果左游標(biāo)遇到重復(fù)值,則移動到該重復(fù)值序列的最右邊(moveRight)

如果右游標(biāo)遇到重復(fù)值,則移動到該重復(fù)值序列的最左邊(moveLeft)

還有一個邊界情況:如果碰到全1的序列呢?moveLeft會一直進(jìn)行下去死循環(huán)了。所以對于這種情況我們?nèi)绻h(huán)一圈發(fā)現(xiàn)還沒有停止moveLeft的意思,就要break掉并且在返回值中進(jìn)行標(biāo)記了。

這個算法的時間復(fù)雜度相對于上個算法有什么變化呢?平均時間復(fù)雜度還是O(log n),但是出現(xiàn)了最壞的情況,全部重復(fù)或者很多重復(fù)的情況。最壞肯定是O(n)啦。上一個算法似乎不會出現(xiàn)這種情況吧。

import java.util.ArrayList; 
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class ShiftFinder2 {
    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) {
            cur = moveLeft(array, cur);
            if (cur == -1) {
                cur = 0;
                break;
            }
            l = moveRight(array, l);
            r = moveLeft(array, r);
            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 = moveRight(array, cur);
                cur = (l + r) / 2;
                continue;
            }
            r = cur;
            cur = (l + r) / 2;
        }
        return array[cur];
    }
    public static int moveLeft(int[] array, int pos) {
        int counter = 0;
        int len = array.length;
        pos = index(pos, len);
        while (true) {
            if (array[pos] != array[index(pos - 1, len)]) {
                return pos;
            }
            if (counter >= len) {
                // special case
                return -1;
            }
            pos = index(pos - 1, len);
            counter++;
        }
    }
    public static int moveRight(int[] array, int pos) {
        int len = array.length;
        pos = index(pos, len);
        while (true) {
            if (array[pos] != array[index(pos + 1, len)]) {
                return pos;
            }
            pos = index(pos + 1, len);
        }
    }
    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 };
        int[] h = { 1, 1, 1, 1, 1, 1 };
        int[] m = { 2, 1, 1, 1, 1, 1, 1 };
        int[] n = { 2, 2, 1, 1, 1, 1, 1, 1, 2 };
        int[] o = { 1, 1, 1, 1, 1, 1, 1, 2 };
        int[] p = { 1, 1, 1, 1, 1, 1, 2, 2 };
        int[] q = { 5, 5, 1, 3, 3, 3, 3, 3, 3, 4 };
        int[] r = { 4, 4, 5, 6, 6, 6, 6, 7, 9, 1, 1, 2 };
        int[] s = { 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
                24, 24, 25, 25, 25, 25, 26, 27, 27, 27, 27, 28, 28, 29, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6,
                6, 7, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14,
                14, 15, 15, 16, 17, 17, 17, 17, 17, 17, 18, 18 };
        int[] t = { 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12, 12, 12, 12, 12, 13, 14, 14, 15, 15, 15, 15,
                16, 16, 17, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22,
                23, 23, 23, 23, 24, 24, 25, 26, 28, 28, 28, 28, 29, 29, 29, 29, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3,
                3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7 };
        int[] u = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1 };
        int[] v = { 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        System.out.println(ShiftFinder2.findMin(a));
        System.out.println(ShiftFinder2.findMin(b));
        System.out.println(ShiftFinder2.findMin(c));
        System.out.println(ShiftFinder2.findMin(d));
        System.out.println(ShiftFinder2.findMin(e));
        System.out.println(ShiftFinder2.findMin(f));
        System.out.println(ShiftFinder2.findMin(g));
        System.out.println(ShiftFinder2.findMin(h));
        System.out.println(ShiftFinder2.findMin(m));
        System.out.println(ShiftFinder2.findMin(n));
        System.out.println(ShiftFinder2.findMin(o));
        System.out.println(ShiftFinder2.findMin(p));
        System.out.println(ShiftFinder2.findMin(q));
        System.out.println(ShiftFinder2.findMin(r));
        System.out.println(ShiftFinder2.findMin(s));
        System.out.println(ShiftFinder2.findMin(t));
        System.out.println(ShiftFinder2.findMin(u));
        System.out.println(ShiftFinder2.findMin(v));
        // gen non-repeatable random shift array
        System.out.println("----- test non-repeatable 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[ShiftFinder2.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("non-repeatable random minimum find: " + ShiftFinder2.findMin(aa));
        System.out.println();
        // gen repeatable random shift array
        System.out.println("----- test repeatable shift array -----");
        attemptSize = 100;
        randomRange = 30;
        shift = rdm.nextInt(attemptSize);
        System.out.println("size: " + attemptSize + "; shift: " + shift);
        List jay = new ArrayList();
        for (int i = 0; i < attemptSize; i++) {
            jay.add(rdm.nextInt(randomRange));
        }
        Collections.sort(jay);
        int[] bb = new int[attemptSize];
        for (int i = 0; i < attemptSize; i++) {
            bb[ShiftFinder2.index(i + shift, attemptSize)] = jay.get(i);
        }
        for (int i = 0; i < attemptSize; i++) {
            System.out.print(bb[i] + " ");
        }
        System.out.println();
        System.out.println("repeatable random minimum find: " + ShiftFinder2.findMin(bb));
        System.out.println();
    }
}

在這里,測試用例也進(jìn)行了增加,盡量覆蓋各種奇葩情況。后面除了不重復(fù)的隨機(jī)移位數(shù)列之外,還有可重復(fù)的隨機(jī)移位序列。

提交的代碼:

public class Solution {
    public 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) {
            cur = moveLeft(array, cur);
            if (cur == -1) {
                cur = 0;
                break;
            }
            l = moveRight(array, l);
            r = moveLeft(array, r);
            if (array[cur] < array[(cur+len-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 = moveRight(array, cur);
                cur = (l + r) / 2;
                continue;
            }
            r = cur;
            cur = (l + r) / 2;
        }
        return array[cur];        
    }
   
    public static int moveLeft(int[] array, int pos) {
        int counter = 0;
        int len = array.length;
        while (true) {
            if (array[pos] != array[(pos+len-1)%len]) {
                return pos;
            }
            if (counter >= len) {
                // special case
                return -1;
            }
            pos = (pos+len-1)%len;
            counter++;
        }
    }
    public static int moveRight(int[] array, int pos) {
        int len = array.length;
        while (true) {
            if (array[pos] != array[(pos+1)%len]) {
                return pos;
            }
            pos = (pos+1)%len;
        }
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66385.html

相關(guān)文章

  • LeetCode 153 有序旋轉(zhuǎn)數(shù)組中找最小-1

    摘要:難度就是說一個從小到大排序好的數(shù)組循環(huán)移位不知多少次,求最小值。數(shù)組無重復(fù)值無重復(fù)的話就比較簡單,用二分查找即可。當(dāng)前游標(biāo)始終是左右游標(biāo)中點(diǎn)位置,與左右游標(biāo)的數(shù)值比較。解法有幾個要點(diǎn)基本終止條件為左邊的數(shù)比當(dāng)前的數(shù)大,那么當(dāng)前數(shù)即是最小值。 Question:Suppose a sorted array is rotated at some pivot unknown to you b...

    MkkHou 評論0 收藏0
  • 70道前端LeetCode題目集合及視頻講解(持續(xù)更新中...)

    前端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 合并兩個有序數(shù)組 167 兩數(shù)之和II - 輸入有序數(shù)組 118 楊輝三角 169 easy 求眾數(shù) 1...

    mayaohua 評論0 收藏0
  • 6-9月技術(shù)文章匯總

    摘要:分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場景說說你常用的命令為什么要有包裝類面向?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)時我在談啥?...

    miya 評論0 收藏0
  • leetcode153-154 find minimum rotated sorted array

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

    DrizzleX 評論0 收藏0
  • [Leetcode] Search in Rotated Sorted Array 搜索旋轉(zhuǎn)有序數(shù)組

    摘要:如果左邊的點(diǎn)比右邊的大,說明這兩個點(diǎn)之間有一個旋轉(zhuǎn)點(diǎn),導(dǎo)致了不再有序。因?yàn)橹挥幸粋€旋轉(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...

    thursday 評論0 收藏0

發(fā)表評論

0條評論

evin2016

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<