25.＜tag-数组和缺失, 重复专题＞-10.03. 搜索旋转数组 + 剑指Offer53 II. 缺失数字 +lt.448. 找到消失数字 + lt- 217, lt-219 重复元素_C

文章目录

lt.面试题 10.03. 搜索旋转数组
剑指 Offer 53 - II. 0～n-1中缺失的数字
lt.448. 找到所有数组中消失的数字
lt- 217. 存在重复元素
lt -219. 存在重复元素 II

lt.面试题 10.03. 搜索旋转数组

[案例需求]

[思路分析]

本题跟lt.33-搜索旋转排序数组大体上是类似的, 因为对一个数组进行再多次的旋转, 都会有部分序列是有序序列, 所以我们是可以使用二分查找的.
具体二分查找的思路是, 因为数组原先是升序排列的, 所以可以如果有部分序列存在 arr[a] <= arr[b], 那么a ~ b就是有序的序列, 利用这个思路我们大体上把数组分为两种情况 :
- if (arr[left] <= arr[mid]) 说明 left --> mid是有序的, 我们向左边进行二分查找
- else就是 (arr[mid] <= arr[right]) 说明 mid—>right是有序的, 我们向右边进行二分查找;
本题可没那么简单, 其他的搜索旋转数组, 都是找到返回就完事了, 这个题目要求我们如果找到了, 返回索引最小的目标元素.
那么我们在使用 nums[mid] == nums[target] 时, 就不能仅仅是return mid这么简单了, 而是需要每次记录下来较小的mid, 记录到ans(自定义的返回变量)中;

[代码实现]

class Solution {
    public int search(int[] arr, int target) {
        // 旋转排序, 因为也是部分有序的, 所以可以使用二分查找
        int len = arr.length;
        int left = 0;
        int right = arr.length -1;

        int ans = Integer.MAX_VALUE;

        while(left <= right){
           
            //有重复
            while(left < right && arr[left] == arr[right]){
                --right;
            }
             int mid = left + ((right - left) >> 1);

            //左边是有序序列
            if(target == arr[mid]){
                ans = Math.min(ans, mid);
            }

            if(arr[left] <= arr[mid]){
                //左边有序(left--->mid)
                if(arr[left] <= target && arr[mid] >= target){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                //右边有序(mid----> right)
                if(arr[mid] <= target && arr[right] >= target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

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

[案例需求]

[思路分析]

原地哈希, 用index映射nums[index]
[代码实现]

class Solution {
    public int missingNumber(int[] nums) {
        //缺失的数字, 原地哈希可解
        // i - nums[i]
        for(int i = 0; i < nums.length; i++){
            if (i != nums[i]){
                return i;
            }
        }

        return nums.length;
    }
}

[思路分析二, 二分查找法]

参见

class Solution {
    public int missingNumber(int[] nums) {
        //二分查找, 左半部分是 nums[i] = i的;
        //右半部分是 nums[i] != i;
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){

            int mid = left + ((right - left) >> 1);
            if(nums[mid] == mid){
                //我要找到的是nums[i] != i的第一个数, 所以我要往右边去
                left = mid + 1;
            }else if(nums[mid] != mid){
                right = mid - 1;
            }
        }

        //遍历结束, left > right, 此时left处于右边届的首位, right处于左边界的末尾
        //而我们需要的是缺失的数字(nums[index] != index), 所以我们返回的是left
        return left;
    }
}

lt.448. 找到所有数组中消失的数字

[案例需求]

[思路分析一, 原地哈希]

原地哈希在数组中用来查找重复的数, 丢失的数还是比较常见的.
我们注意到题目条件: 数组中数据范围1-n连续, 而数组索引则是index: 0 ~ n - 1;
所以, 我们会想到用索引来映射数组中的值, 映射方法: index + 1 对应于 nums[index];
那么数组中一个数的对应索引为: targetIndex = nums[index] - 1
[代码实现]

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
		int len = nums.length - 1;
		int index = 0;
		
		while(index < len){
			int targetIndex = nums[index] - 1;  // nums[i]实际应该存储的位置

			if(nums[index] == nums[targetIndex]){  // idex 处是正确的值
				++index;
			}else{
				swap(nums, index, targetIndex);
			}
		}
		//把数组中的数交换到应该存放的位置,
		List<Integer> list = new ArrayLst<>();
		
		for(int i = 0; i < len; i++){
			if(nums[i] != i){
				list.add(i + 1);
			}
		}
	}
}

[思路分析二, 标记法]

看下面注释, 本题可以作为一类题目的通用解法, 还是非常好用的.
类似题目: 23.＜tag-数组和原地哈希＞-lt.442. 数组中重复的数据 + lt.lt- 268. 丢失的数字

//1. 标记法
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //标记法, 遍历数组, 把遇到的数- 1 作为索引去访问, 并加上标记
        // 如果遇到相同的数, 那么这个标记一定会被访问到, 这样可以用来找到数组中分重复的数字;
        //没被访问到的地方就是缺失数字的地方(因为这个缺失数字的索引我们计算不到)
        //我们只需把这个索引 + 1就得到了缺失的数字, 注意这种加负号标记的只适合不存在重复数字的情况;
        
        //本体由于存在重复数字, 所以更换一种标记方式
        // 给每个遍历到的数 + n. 这样缺失数所对应索引出的数就会 < n;

        int len = nums.length; 

        for(int i = 0; i < len; i++){
            int targetIndex = (nums[i] - 1) % len; //%n是为了使targetIndex 落在 0 ~ len -1 内

            nums[targetIndex] += len;
        }

        List<Integer> list = new ArrayList<>();

        for(int i = 0; i < len; i++){
            if(nums[i] <= len)
                list.add(i + 1);
        }

        return list;
    }
}

lt- 217. 存在重复元素

[案例需求]

[思路分析一, 哈希表]

先存入一个元素到哈希表, 然后遍历数组, 与哈希表中数进行比较, 发现重复即可返回true;
注意: 这里可以用hashMap, 也可以用各种list, set.
[代码实现]

// 使用内建库
class Solution {
    public boolean containsDuplicate(int[] nums) {
        //剪枝
        int len = nums.length;
        if(len < 2)return false;
        
        // 哈希表
        Set<Integer> set = new HashSet<>();

        set.add(nums[0]);
        for(int i = 1; i < len; i++){
            if(set.contains(nums[i])){
                return true;
            }else{
                set.add(nums[i]);
            }
            
        }

        return false;
    }
}

[思路分析二, 排序两两比较]

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++){
            if(i + 1 < nums.length && nums[i] == nums[i + 1])return true;
        }

        return false;
    }
}

拓展题目

lt -219. 存在重复元素 II

[案例需求]

[思路分析]

[代码示例]

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //hashMap
        //遍历数组. 存在且索引相差 > k
        Map<Integer, Integer> map = new HashMap<>();

        int len = nums.length;
        if(len < 2)return false;

        map.put(nums[0], 0);

        for(int i = 1; i < len; i++){
            if(map.containsKey(nums[i]) && Math.abs(map.get(nums[i]) - i) <= k){
                return true;
            }else{
                map.put(nums[i], i);
            }
        }

        return false;
    }
}