Leetcode – Sword refers to Offer 53 – I. Looks for the number I in the sorted array
[Blog link]
The path to learning at 🐔
The nuggets home page
[B].
Count the number of occurrences of a number in a sorted array. Example 1: input nums = [5,7,7,8,8,10], target = 8 output: 2 example 2: input nums = [5,7,7,8,8,10], target = 6 output: 0 limit: 0 <= Array length <= 50000 https://leetcode-cn.com/problems/find-first-and-last- position-of-element-in-sorted-array/ Related Topics Array binary lookup 👍 170 👎 0Copy the code[答 案]
Leetcode topic link
[making address]
Code link
[introduction]
Idea 1: Violence
- The brute force method is too easy. Just scan the O(n) once. I’m not going to write it
Time complexity O(n)
Idea 2: Two
- First scan to the starting point, then narrow down to the right
public int search(int[] nums, int target) { //corner case if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) { return 0; } int n = nums.length, l = 0, r = n - 1,start = 0; While (l < r) {int mid = (l - r + 1) / 2 + r; if (nums[mid] >= target) { if (nums[mid] == target) { if (mid == 0 || nums[mid - 1] < target) { l = mid; break; } } r = mid - 1; } else { l = mid; }} // Return 0 if the current element is not found; if (nums[l] ! = target) { return 0; } r = n - 1; r = n - 1; start = l; while (l < r) { int mid = (l - r + 1) / 2 + r; if (nums[mid] == target) { if (mid == n - 1 || nums[mid + 1] > target) { r = mid; break; } l = mid; }else{ r = mid - 1; } } return r - start + 1; }Copy the code