FilesExpand file tree

 master

/

offer53.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (45 loc) · 1.72 KB

 master

/

offer53.java

Copy path

Top

File metadata and controls

• Code
• Blame

48 lines (45 loc) · 1.72 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* [53-I] 在排序数组中查找数字

*

* 题目: 统计一个数字在排序数组中出现的次数.

*

* 思路: 二分查找返回不大于目标元素的最后一个元素, 即将数组分为小于等于目标元素的区间和大于目标元素的区间, 返回前一个区间的最后一个元素.

* 语义约定: a. 当有多个目标元素时, 必须返回最靠后的元素.

* b. 失败时, 应返回小于目标元素的最大者(含哨兵 (lo - 1)).

* 使用二分查找目标元素 -1 得到的下标 +1 和目标元素的下标之间即为目标数字出现范围.

*/

class Solution {

/**

* 时间复杂度: O(logn)

* 空间复杂度: O(1)

*/

public int search(int[] nums , int target) {

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

return 0;

}

// use binary search to find target element,

// if success, will return right lastPos,

// if failure, will return -1 or n - 1,

// so need judge current return index is right or not.

int lastPos = binarySearch(nums, target);

if (lastPos == -1 || nums[lastPos] != target) {

return 0;

}

// find target - 1 for get the first element index in front of target.

int firstPosPre = binarySearch(nums, target - 1);

return lastPos - firstPosPre;

}

// return the last target element.

private int binarySearch(int[] nums, int target) {

int lo = 0, hi = nums.length - 1;

while (lo <= hi) {

int mid = lo + ((hi - lo) >> 1);

if (nums[mid] <= target) {

lo = mid + 1;

} else {

hi = mid - 1;

}

}

return hi;

}

}