This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Topic describes

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/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • The problem is easy to understand and can be solved in many ways. It can be solved by simple solution, binary solution, Stream solution and other methods.
  • The Stream solution is a new API in Java 8. Although Java 8 is the de facto standard, Stream is still not used much, so we can use it more.
  • Stream provides a high-level abstraction of Java collection operations and expressions in an intuitive manner similar to querying data from a database with SQL statements. Let programmers write efficient, clean, concise code.
  • This problem mainly uses the filter count method to make our code more concise.

code

  • Simple solution
    public int search(int[] nums, int target) {
        int ans = 0;
        for (int num : nums) {
            if(num == target) { ans++; }}return ans;
    }
Copy the code
  • Binary solution
public int search(int[] nums, int target) {
            int ans = 0;
            int left = 0;
            int n = nums.length;
            int right = n - 1;
            int idx = -1;

            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    idx = mid;
                    break;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1; }}if (idx > -1) {
                for (int i = idx - 1; i >= 0; i--) {
                    if(nums[idx] ! = target) {break;
                    } else{ ans++; }}for (int i = idx ; i < n; i++) {
                    if(nums[idx] ! = target) {break;
                    } else{ ans++; }}}return ans;
        }
Copy the code
  • The stream method
    public int search(int[] nums, int target) {
        return (int) Arrays.stream(nums).filter(num -> (num == target)).count();
    }
Copy the code

conclusion

  • The time complexity of the naive solution is O(n), the space complexity is O(1).
  • The binary solution is order log of n in time, order one in space.
  • The time complexity of the STREAM solution is O(n) and the space complexity is O(1).
  • Adhere to the algorithm of the day, come on!