leetcode1095. 山脉数组中查找目标值-二分法

leetcode1095. 山脉数组中查找目标值-二分法

五月 23, 2020

leetcode1095. 山脉数组中查找目标值

给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index，就请返回 -1。

何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：

首先，A.length >= 3
其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

  • A[0] < A[1] < … A[i-1] < A[i]
  • A[i] > A[i+1] > … > A[A.length - 1]

你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：

MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
MountainArray.length() - 会返回该数组的长度

注意：

对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

示例 1：
输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。

示例 2：
输入：array = [0,1,2,4,2,1], target = 3
输出：-1
解释：3 在数组中没有出现，返回 -1。

提示：
3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9

这里面每行条件都有用，开始因为没仔细读就想复杂了。

二分法

我开始还以为可以出现[1,3,3,2,1]这种，或者[1,2,2,3,1]这种。但是题里面说了只有大于小于，想复杂了。
看着长，其实就是3次二分，第一次不太好找，后两次是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */
 
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int left = 0, right = mountainArr.length() - 1;
        int ll = left, rr = right;
        int top = 0;
        int ans = 0;
        while (ll <= rr) {//第一步找出山顶
            int mid = (ll + rr) >> 1;
            int midl = mid - 1, midr = mid + 1;//防止越界，因为我没做过162，完全是现想的
            if (mid - 1 >= 0) midl = mid - 1;
            if (mid + 1 < mountainArr.length()) midr = mid + 1;
            if (mountainArr.get(mid) > mountainArr.get(midl) && mountainArr.get(mid) > mountainArr.get(midr)) {
                top = mid;
                break;
            }
            if (mountainArr.get(midl) < mountainArr.get(midr)) {
                ll = mid + 1;
            } else {
                rr = mid - 1;
            }
        }
        //System.out.println("top = "+top);
        ans = binUpSearch(0,top,mountainArr,target);//先二分左边
        if (ans == -1) {
             //左边查不到在去search右边，因为升序和降序的二分有一点差别，所以重新一遍降序的
            ans = binDownSearch(top,mountainArr.length() - 1,mountainArr,target);
        }
        
        return ans;
    }
    
    public int binDownSearch(int left, int right, MountainArray mountainArr, int target) {
        if (left > right) {
            return -1;
        }
        int l = left, r = right;
        int situation = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cur = mountainArr.get(mid);
            if (cur == target) {
                return mid;
            }
            if (cur < target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            
        }
        return -1;
    }
    public int binUpSearch(int left, int right, MountainArray mountainArr, int target) {
        if (left > right) {
            return -1;
        }
        int l = left, r = right;
        int situation = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cur = mountainArr.get(mid);
            if (cur == target) {
                return mid;
            }
            if (cur < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
            
        }
        return -1;
    }
}

leetcode 90/100