第四天——查找算法(简单)

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

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。

数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。


我头一次用例全过但是超时的题目

注意下面这个是我翻车的做法

不知道有没有人跟我一样想到双指针去的

public class Solution {
    public int FindRepeatNumber(int[] nums) {
        int n = nums.Length;
        int left = 0;
        int right = n-1;

        while(left <= right)
        {
            if(left == right && left != n-1)
            {
                left++;
                right = n-1;
            }
            if(nums[left] == nums[right])
            {
                return nums[left];
            }
            else
            {
                right--;
            }
        }

        return -1;
    }
}

事实证明我还是想的太复杂了


原地交换

public class Solution {
    public int FindRepeatNumber(int[] nums) {
        for(int i=0;i<nums.Length;i++)
        {
            while(nums[i]!=i)
            {
                if(nums[i]==nums[nums[i]]) return nums[i];
                int temp = nums[i];
                nums[i]=nums[nums[i]];
                nums[temp]=temp;
            }
        }
        return -1;
    }
}

条件中说明了所有数字都在 0~n-1 的范围内

那么我们可以尝试着从0到n-1每个数字都和数组对应下标的数字比较

如果不相等的话再判断数组对应下标的数字是否和以这个数为下标的数相等

如果相等那就重复了直接返回

如果不相等交换i和下标下的数字,目的是为了让数字放在匹配的下标的地方


神奇的桶排序

看到大佬写的非常神奇的方法

数组长度限制在100000

直接新建一个长度100000数组arr

如果某个数字num出现,arr[num]的值+1

因此只要arr[num]>1,就说明它重复了

public class Solution {
    public int FindRepeatNumber(int[] nums) {
        int[] arr=new int[100000];
        for(int i=0;i<nums.Length;i++){
            arr[nums[i]]++;
            if(arr[nums[i]]>1)
                return nums[i];
        }
        return 0;
    }
}

作者:hugo-27
链接:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/c-shi-kong-shuang-100-by-hugo-27/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

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

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

示例 1:

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

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

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

        int score = 0;
        for(int i=0;i<nums.Length;i++)
        {
            if(nums[i] == target)
            {
                score++;
            }
        }

        return score;
        
    }
}

最简单直观的方法肯定是像上面这样

但是没有利用到升序的条件

所以这道题实际上想考察的应该是二分法


重复出现的数字只会排在一起

所以重复的数字就有最左边和最右边之分

那么重复次数就是最右下标-最左下标+1

不要被Search函数里一大段判断条件吓到

实际上就是最左<最右<长度

并且两个值都等于目标值

就确定了区间

关键在下面二分查找的函数

lower这个布尔变量是为了代码复用而存在

如果是true,查找的就是第一个大于等于目标值的下标

如果是false,查找的就是第一个大于目标值的下标

所以上面search函数里的right要减1

不然最右值就错了

public class Solution {
    public int Search(int[] nums, int target) {
        int leftIdx = BinarySearch(nums, target, true); 
        int rightIdx = BinarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.Length && 
        nums[leftIdx] == target&&nums[rightIdx] == target) 
        {
            return rightIdx - leftIdx + 1;
        } 
        return 0;
    }

    public int BinarySearch(int[] nums, int target, bool lower) {
        int ans = nums.Length;
        int left = 0;
        int right = nums.Length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target))
            {
                right = mid - 1;
                ans = mid;
            } 
            else 
            {
                left = mid + 1;
            }
        }
        return ans;
    }
}

剑指 Offer 53 – II. 0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        int left = 0;
        int right = n-1;

        while(left<=right)
        {
            int mid = (left+right)/2;
            if(nums[mid] == mid) left = mid+1;
            else right = mid -1;
        }

        return left;
    }
}

有序数列的搜索优先考虑二分法

这是我今天学到的东西

要注意长度不是n而是n-1

所以这题不能想当然的认为直接判断下标和元素值是不是相等

需要用二分法来减少搜索范围

思路

left从0开始right从长度-1开始

当left<=right的时候找mid

判断以mid为下标的元素值和mid是不是相等

如果相等范围就要往右缩小,left = mid+1

反之不相等就要往左缩,right = left -1

最后因为left <= right,输出哪个都无所谓

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注