长大后想做什么？做回小孩！

0%

LeetCode——山脉数组中查找目标值

发表于 分类于 Valine：
本文字数： 280

NO.1095 山脉数组中查找目标值 困难

Jo1aOx.png

Jo1U61.png

思路一：二分法 这道题思路上没有太多迟疑，”有序数组中找目标”而且还”get不能超过100次”疯狂暗示二分法！先准备好题目中所说的接口和实现：

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
public interface MountainArray {

    public int get(int index);

    public int length();

}

public class MountainArrayImpl implements MountainArray {
    private int[] arr;
    private int size;

    public MountainArrayImpl(int[] arr) {
        this.arr = arr;
        this.size = this.arr.length;
    }

    @Override
    public int get(int index) {
        return this.arr[index];
    }

    @Override
    public int length() {
        return this.size;
    }

}

开始解题：先找到山顶元素下标idx，所谓山顶元素就是大于前一个元素并且小于后一个元素；然后数组分成了左右两部分，先在左边部分的升序区间[0,idx-1]二分查找target；如果左边没有，再去右边部分的降序区间[idx+1,length-1]二分查找target；都没有则返回-1。

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
public int findInMountainArray(int target, MountainArray mountainArr) {
    int len = mountainArr.length();
    //二分法找山顶下标
    int left = 0, right = mountainArr.length() - 1;
    while (left < right) {
        int mid = left + ((right - left) >>> 1);
        //小于右边的元素,说明mid在升序部分,向右收缩搜索区间
        if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    int topIdx = left;
    //二分法到左边部分找
    int lResult = findInLeft(mountainArr, 0, topIdx - 1, target);
    //如果左边部分没有,检查target是否是山顶元素
    if (lResult != -1) {
        return lResult;
    } else if (mountainArr.get(topIdx) == target) {
        return topIdx;
    }
    //左边和山顶都没有，到右边部分二分法
    int rResult = findInRight(mountainArr, topIdx + 1, len - 1, target);
    return rResult;
}

private int findInRight(MountainArray mountainArr, int left, int right, int target) {
    while (left <= right) {
        int mid = left + ((right - left) >>> 1);
        if (mountainArr.get(mid) == target) {
            return mid;
        } else if (mountainArr.get(mid) < target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

private int findInLeft(MountainArray mountainArr, int left, int right, int target) {
    while (left <= right) {
        int mid = left + ((right - left) >>> 1);
        if (mountainArr.get(mid) == target) {
            return mid;
        } else if (mountainArr.get(mid) > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

时间复杂度：O(logn) 三次二分法。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github