<> Interview questions 53 - I. Find numbers in sort array I
Count the number of times a number appears in the sort 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
<> Simple violence solution
class Solution { public int search(int[] nums, int target) { int sum=0; for(int
i=0;i<nums.length;i++){ if(nums[i]==target){ sum++; } } return sum; } }
<> Dichotomy search
Because arrays are sorted arrays , So we can find the left and right boundaries first , Find the left and right bounds in the array , And then you can get that number by subtracting .
/** * @Auther: truedei * @Date: 2020 /20-5-20 08:45 * @Description: */ public
class Test1 { static public int search(int[] nums, int target) { int i=0; int j=
nums.length-1; int left=0,right=0; // Search left border while (i<=j){ int mid = (i + j) /2;
if(nums[mid] <= target) i = i + 1; else j = j - 1; } right = i; i = 0; j=nums.
length-1; // Search right boundary while (i<=j){ int mid = (i + j) /2; if(nums[mid] < target) i =
i+ 1; else j = j - 1; } left=j; return right - left - 1; } public static void
main(String[] args) { int nums[] = new int[]{5,7,7,8,8,10},target = 8; System.
out.println(search(nums,target)); } }
Technology
Daily Recommendation