GeezerVison is showing github.com — leet-code/Java/IndexMatch.java at master · awangdev/leet-code

Expand file tree

IndexMatch.java

Copy path

More file actions

Latest commit

History

executable file

54 lines (45 loc) · 1.55 KB

IndexMatch.java

Copy path

File metadata and controls

executable file

54 lines (45 loc) · 1.55 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

有序, 假设有这样的数字:target.

target 左边的数字，一定不比index大，target右边的数字，一定比index大。

这样可以binary search.O(logn)

```

来自网上uber面经：给一个有序数组（不含重复），返回任意一个数字，这个数字的值和它的数组下标相等

可能的follow up:

1. 如果含有重复数字怎么办？

如果有序，也没问题，还是binary search

2. 另一种follow up:找这样数字的边界.

如果存在，那么和index match的一定在一块.

找到任何一个candiate, 找边界，也可以binary search,只是match的condition不同罢了。

//Binary search.

import java.io.*;

import java.util.*;

class Solution {

public int indexMatch(int[] nums) {

if (nums == null || nums.length == 0) {

return -1;

}

int start = 0;

int end = nums.length - 1;

while (start + 1 < end) {

int mid = start + (end - start)/2;

if (nums[mid] == mid) {

return mid;

} else if (nums[mid] < mid) {

start = mid;

} else {//nums[mid] > mid

end = mid;

}

return -1;

}

public static void main(String[] args) {

System.out.println("START");

int[] input = {-1, 0, 1, 3, 5, 8, 9};//return 3

Solution sol = new Solution();

int rst = sol.indexMatch(input);

System.out.println(rst);

}

```