第4天 查找算法（简单）

发表于 | 分类于
字数统计: 491 | 阅读时长 ≈ 2

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

题解

思路一

HashSet

循环地将数组中的元素放入Set中,放不进去说明就重复了

1
2
3
4
5
6
7
8
9
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> help = new HashSet<Integer>();
        for(int n : nums)
            if(!help.add(n))
                return n;
        return -1;
    }
}

思路二

暴力法,直接用每个元素查,复杂度太高

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int findRepeatNumber(int[] nums) {
        int len = nums.length;
        for(int i = 0; i < len-1; i++)
            for(int j = i+1; j < len; j++)
                if(nums[i] == nums[j])
                    return nums[i];
        return -1;
    }
}

思路三

使用Java内置的Arrays.sort()方法进行排序,然后遍历一遍就行了,Java的排序方法是快速排序,一般为O(nlogn)效率比较高,遍历的时候,复杂度是O(n)

1
2
3
4
5
6
7
8
9
class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int n = 1; n < nums.length; n++)
            if(nums[n] == nums[n-1])
                return nums[n];
        return -1;
    }
}

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

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

示例 1:

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

示例 2:

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

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

题解

思路一

直接找,复杂度为O(n)

1
2
3
4
5
6
7
8
9
class Solution {
    public int search(int[] nums, int target) {
        int res = 0;
        for(int n : nums)
            if(n == target)
                res++;
        return res;
    }
}

思路二

二分查找,O(logn)

1