53 - I. 在排序数组中查找数字 I

2022-03-03 本文已影响0人木木与呆呆

链接

https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
难度： #简单

题目

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

提示：

0 <= nums.length <= $10^5$
$-10^9$ <= nums[i] <= $10^9$
nums 是一个非递减数组
$-10^9$ <= target <= $10^9$

代码框架

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

    }
}

题目解析

辅助思考图形：
[[剑指 Offer 53 - I. 在排序数组中查找数字 I.drawio]]
解答思路1：
暴力解法，从数组头部开始循环，
比较目标数据，计算目标的出现次数，
如果数组的数据大于目标数据，则结束循环。

解答思路2：
使用二分查找法，
递归查找数组，
首先根据low和high的值二分为mid，
和target的比较确定范围，
如果找到了目标，则则计数器加1，
且在mid的前后查找和target相同的元素。

解答思路3：
使用二分查找法，
while循环查找数组，
如果找到目标，
则在附近查找重复的元素。

解答思路4：
使用二分查找法，
while循环查找数组，
第一遍循环，
找出第一个等于target的下标tFirst,
第二遍循环，
找出最后一个等于target的下标tLast;
target的数量就是tLast-tFirst+1。

测试用例

package edu.yuwen.sowrd.num53_I.solution;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import edu.yuwen.sowrd.num53_I.sol4.Solution;

/**
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 */
public class SolutionTest {
    @Test
    public void testCase1() {
        Solution solution = new Solution();

        int[] nums = { 5, 7, 7, 8, 8, 10 };
        int target = 8;
        int count = solution.search(nums, target);

        Assertions.assertEquals(2, count);
    }

    /**
     * 输入: nums = [5,7,7,8,8,10], target = 6
     * 输出: 0
     */
    @Test
    public void testCase2() {
        Solution solution = new Solution();

        int[] nums = { 5, 7, 7, 8, 8, 10 };
        int target = 6;
        int count = solution.search(nums, target);

        Assertions.assertEquals(0, count);
    }

    /**
     * 输入: nums = [1,4], target = 4
     * 输出: 1
     */
    @Test
    public void testCase3() {
        Solution solution = new Solution();

        int[] nums = { 1, 4 };
        int target = 4;
        int count = solution.search(nums, target);

        Assertions.assertEquals(1, count);
    }

    /**
     * 输入: nums = [1,2,3,3,3,3,4,5,9], target = 3
     * 输出: 4
     */
    @Test
    public void testCase4() {
        Solution solution = new Solution();

        int[] nums = { 1, 2, 3, 3, 3, 3, 4, 5, 9 };
        int target = 3;
        int count = solution.search(nums, target);

        Assertions.assertEquals(4, count);
    }
}

解答1

package edu.yuwen.sowrd.num53_I.sol1;

public class Solution {
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if (cur == target) {
                count++;
            }
            if (cur > target) {
                break;
            }
        }

        return count;
    }
}

解答2

package edu.yuwen.sowrd.num53_I.sol2;

public class Solution {
    int count = 0;
    int target;

    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        this.target = target;

        int low = 0;
        int high = nums.length - 1;
        binarySearchRecurve(nums, low, high);

        return count;
    }

    private void binarySearchRecurve(int[] nums, int low, int high) {
        // 结束二分查找
        if (low > high) {
            return;
        }

        int mid = (low + high) / 2;
        // 找到目标后，查找附近和目标相等的元素
        if (target == nums[mid]) {
            count++;
            searchNearBy(nums, mid);
            // 结束查找
            return;
        }
        // 目标小于中间值，则查找左半边部分
        if (target < nums[mid]) {
            high = mid - 1;
        }
        // 目标大于中间值，则查找右半边部分
        if (target > nums[mid]) {
            low = mid + 1;
        }

        binarySearchRecurve(nums, low, high);
    }

    /**
     * 在指定索引的前后两边查找target
     */
    private void searchNearBy(int[] nums, int mid) {
        // 先搜索左边
        int left = mid - 1;
        while (left >= 0) {
            if (target == nums[left]) {
                count++;
                left--;
                continue;
            }
            // target不相等了，则停止搜索
            break;
        }

        // 再搜索右边
        int right = mid + 1;
        while (right < nums.length) {
            if (target == nums[right]) {
                count++;
                right++;
                continue;
            }
            // target不相等了，则停止搜索
            break;
        }
    }
}

解答3

package edu.yuwen.sowrd.num53_I.sol3;

public class Solution {
    int count = 0;
    int target;

    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        this.target = target;

        int low = 0;
        int high = nums.length - 1;
        binarySearchLoop(nums, low, high);
        return count;
    }

    private void binarySearchLoop(int[] nums, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            // 找到目标target，则统计前后所有的target的数量
            if (target == nums[mid]) {
                count++;
                searchNearBy(nums, mid);
                return;
            }

            // 目标小于中间值，则查找左半边部分
            if (target < nums[mid]) {
                high = mid - 1;
            }
            // 目标大于中间值，则查找右半边部分
            if (target > nums[mid]) {
                low = low + 1;
            }
        }

    }

    /**
     * 查找index前后和target相同的元素
     */
    private void searchNearBy(int[] nums, int index) {
        int left = index - 1;
        while (left >= 0) {
            // 不相等就停止查找
            if (target != nums[left]) {
                break;
            }
            count++;
            left--;
        }

        int right = index + 1;
        while (right < nums.length) {
            // 不相等就停止查找
            if (target != nums[right]) {
                break;
            }
            count++;
            right++;
        }
    }
}

解答4 推荐

package edu.yuwen.sowrd.num53_I.sol4;

public class Solution {
    int target;

    int tFirst = -1;
    int tLast = -1;

    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        this.target = target;

        int low = 0;
        int high = nums.length - 1;
        binarySeachFirst(nums, low, high);
        binarySeachLast(nums, low, high);

        if (tFirst != -1 && tLast != -1) {
            return tLast - tFirst + 1;
        }
        return 0;
    }

    /**
     * 二分搜索第一个等于target的下标
     */
    private void binarySeachFirst(int[] nums, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (target == nums[mid]) {
                // 确保找到最左边
                if (mid == 0 || nums[mid - 1] != target) {
                    tFirst = mid;
                    break;
                }
                // 否则进一步查找左边的部分
                else {
                    high = mid - 1;
                }
            }

            // 如果目标小于中间值，则查找左半边部分
            if (target < nums[mid]) {
                high = mid - 1;
            }

            // 如果目标值大于中间值，则查找右半边部分
            if (target > nums[mid]) {
                low = mid + 1;
            }
        }
    }

    /**
     * 二分搜索最后一个等于target的下标
     */
    private void binarySeachLast(int[] nums, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            // 该处逻辑是和binarySeachFirst的唯一区别
            if (target == nums[mid]) {
                // 确保找到最右边
                if (mid == nums.length - 1 || nums[mid + 1] != target) {
                    tLast = mid;
                    break;
                }
                // 否则进一步查找右边的部分
                else {
                    low = mid + 1;
                }
            }

            // 如果目标小于中间值，则查找左半边部分
            if (target < nums[mid]) {
                high = mid - 1;
            }
            // 如果目标值大于中间值，则查找右半边部分
            if (target > nums[mid]) {
                low = mid + 1;
            }
        }
    }
}

53 - I. 在排序数组中查找数字 I

链接

题目

代码框架

题目解析

测试用例

解答1

解答2

解答3

解答4 推荐

猜你喜欢

热点阅读