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

資訊專欄INFORMATION COLUMN

[Lintcode] Find Peak Element 找峰值

leiyi / 2104人閱讀

摘要:找出該矩陣的一個峰值元素,返回他的坐標原題鏈接一維二分搜索復雜度時間空間思路最直觀的方法是遍歷整個矩陣,但這要的時間。

Find Peak Element I

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note: Your solution should be in logarithmic complexity.

原題鏈接

順序遍歷 復雜度

時間 O(N) 空間 O(1)

思路

最簡單的做法,遍歷數組找出比前后都大的元素。

代碼
public class Solution {
    public int findPeakElement(int[] nums) {
        for(int i = 1; i < nums.length-1; i++){
            if(nums[i] > nums[i+1] && nums[i] > nums[i-1]){
                return i;
            }
        }
        return nums.length <= 1 || nums[0] > nums[1] ? 0 : nums.length-1;
    }
}
二分搜索 復雜度

時間 O(logN) 空間 O(1)

思路

題目要求時間復雜度為O(logN),logN時間的題目一般都是Heap,二叉樹,分治法,二分搜索這些很“二”解法。這題是找特定元素,基本鎖定二分搜索法。我們先取中點,由題意可知因為兩端都是負無窮,有上坡就必定有一個峰,我們看中點的左右兩邊大小,如果向左是上坡,就拋棄右邊,如果向右是上坡,就拋棄左邊。直到兩邊都小于中間,就是峰了。

代碼
public class Solution {
    public int findPeakElement(int[] nums) {
        for(int min = 0, max = nums.length -1, mid = max / 2 ; min < max ; mid = (min + max) / 2){
            if(min == mid) return nums[min] < nums[max] ? max : min;
            min = nums[mid] < nums[mid+1] ? mid : min;
            max = nums[mid] > nums[mid+1] ? mid : max; 
        }
        return 0;
    }
}
Find Peak Element II

一個整數矩陣有如下一些特性:

相鄰的整數都是不同的 矩陣有 n 行 m 列。 對于所有的 i < m, 都有 A0 < A1 && An - 2 > An - 1. 對于所有的 j < n, 都有 Aj < Aj && Aj > Aj. 我們定義一個位置 P 是一個峰,如果有 Aj > Aj+1 && Aj > Aj-1 && Aj > Aj && Aj > Aj。

找出該矩陣的一個峰值元素,返回他的坐標

原題鏈接

一維二分搜索 復雜度

時間 O(MlogN) 空間 O(1)

思路
1    2    3    4    5
16    41    25    22    6
15    17    24    21    7
14    18    19    20    8
13    12    11    10    9

最直觀的方法是遍歷整個矩陣,但這要O(MN)的時間。對于二維數組,我們也可以使用二分搜索法。比如,我們按照行二分搜索(意思是在1、2、3、4、5行中取得第3行),然后遍歷這行找到這行的峰值,比如第3行是24。然后看24的上下兩個元素的大小,這里24比19大,但是比25小,可知1、2行中肯定有答案(因為24到25是一個上坡,上坡方向必有解)。所以我們拋棄第3、4、5行,再在1、2行中重復這個二分搜索,直到找到結果。

代碼
class Solution {
    public List findPeakII(int[][] A) {
        // write your code here
        List res = new ArrayList();
        int min = 0, max = A.length - 1, mid = max / 2;
        while(min <= max){
            //對行進行二分
            mid = min + ((max - min) >> 1);
            //找出中間行的峰值
            int col = findPeak(mid, A);
            //判斷二分前進方向
            if(A[mid][col] < A[mid + 1][col]){
                min = mid + 1;
            } else if (A[mid][col] < A[mid - 1][col]){
                max = mid - 1;
            } else {
            //四周都較小則返回結果
                res.add(mid);
                res.add(col);
                return res;
            }
        }
        return res;
    }
    
    private int findPeak(int row, int[][] A){
        int peak = 0;
        for(int i = 1; i < A[row].length; i++){
            if(A[row][i]>A[row][peak]){
                peak = i;
            }
        }
        return peak;
    }
}
二維二分搜索 復雜度

時間 O(2M+N) 空間 O(1)

思路
1    2    3    4    5
16    41    25    22    6
15    17    24    21    7
14    18    19    20    8
13    12    11    10    9

我們還可以依次對行和列都進行二分搜索,進一步降低時間復雜度。比如我們先選到第3行,找到24作為本行最大后,發現應該向上前進,所以在比24上方的區域,也就是完整的1、2行,對列進行二分,找到第三列(這個第三列是只有1、2行的第三列,3、4、5行已經被拋棄),找出第三列的兩行中最大值25,發現左邊的41大于25,所以3、4、5列被拋棄。現在還剩下前兩行的前兩列,再在這個區域對行二分,找出的是第1行,以此類推,最后當mid == min 時,結果肯定在min和max之中。

代碼
class Solution {
    public List findPeakII(int[][] A) {
        // write your code here
        List res = new ArrayList();
        //初始化行的二分邊界,還有列的二分邊界
        int rowmin = 0, rowmax = A.length - 1, rowmid = rowmax / 2;
        int colmin = 0, colmax = A[0].length - 1, colmid = colmax / 2;
        while(rowmin <= rowmax && colmin <= colmax){
            //計算行的二分中點
            rowmid = rowmin + ((rowmax - rowmin) >> 1);
            int rowpeak = findRowPeak(rowmid, A, colmin, colmax);
            if(A[rowmid][rowpeak] < A[rowmid + 1][rowpeak]){
                rowmin = rowmid + 1;
            } else if (A[rowmid][rowpeak] < A[rowmid - 1][rowpeak]){
                rowmax = rowmid - 1;
            } else {
                res.add(rowmid);
                res.add(rowpeak);
                return res;
            }
            //計算列的二分中點
            colmid = colmin + ((colmax - colmin) >> 1);
            int colpeak = findColPeak(colmid, A, rowmin, rowmax);
            if(A[colpeak][colmid] < A[colpeak][colmid + 1]){
                colmin = colmid + 1;
            } else if (A[colpeak][colmid] < A[colpeak][colmid - 1]){
                colmax = colmid - 1;
            } else {
                res.add(colpeak);
                res.add(colmid);
                return res;
            }
        }
        return res;
    }
    
    private int findRowPeak(int row, int[][] A, int start, int end){
        int peak = 0;
        for(int i = start; i <= end; i++){
            if(A[row][i]>A[row][peak]){
                peak = i;
            }
        }
        return peak;
    }
    
    private int findColPeak(int col, int[][] A, int start, int end){
        int peak = 0;
        for(int i = start; i <= end; i++){
            if(A[i][col]>A[peak][col]){
                peak = i;
            }
        }
        return peak;
    }
}

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

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

相關文章

  • Find Peak Element

    摘要:題目鏈接這道題給了條件,然后兩端是負無窮。因為只要知道當前點是遞增的,只要往右邊找肯定能找到,大不了到最后,因為是永遠小于當前點的。 Find Peak Element 題目鏈接:https://leetcode.com/problems... 這道題給了條件:nums[i] != nums[i+1],然后兩端是負無窮。所以能用binary search做。因為只要知道當前點是遞增的,...

    付永剛 評論0 收藏0
  • [LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

    摘要:一種是利用去找同一層的兩個邊,不斷累加寄存。雙指針法的思想先找到左右兩邊的第一個峰值作為參照位,然后分別向后向前每一步增加該位與參照位在這一位的差值,加入,直到下一個峰值,再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

    bluesky 評論0 收藏0
  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

    摘要:排序數組中找最小值或最大值的題目,很明顯可以使用二分法。因此,只判斷終點和中點元素的大小關系即可。這里有一種情況是上述后三個,中點值和末位相等。此時,兩邊同時遞歸,并返回兩邊遞歸值的較小值。當首位和末位重合,說明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

    cgh1999520 評論0 收藏0
  • [LeetCode/LintCode] Top K Frequent Words

    LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

    0x584a 評論0 收藏0
  • [Leetcode] Find Minimum in Rotated Sorted Array

    摘要:二分迭代法復雜度時間空間遞歸棧空間思路找旋轉數組的起點,實際上類似找一個山谷,只要兩邊都比中間高就對了,這和這題很像。 Find Minimum 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 ...

    notebin 評論0 收藏0

發表評論

0條評論

leiyi

|高級講師

TA的文章

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