31天刷完剑指offer——(第4天) 查找算法

#pragma once
#include<vector>
#include<algorithm>
#include<unordered_set>

using std::unordered_set;
using std::vector;

/* 排序，双指针（时间复杂度N*logN，空间复杂度1）

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {

        std::sort(nums.begin(), nums.end());
        for (int i = 1, j = 0; i < nums.size(); ++i, ++j) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }

        return INT_MAX;
    }
};

*/


/* 哈希表（时间复杂度N，空间复杂度N）

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> hash;         // 哈希表用来存储遍历过的数字
        for (auto x : nums) {                      // 遍历数组
            if (hash.find(x) != hash.end()) {      // 如果在hash中找到x，说明重复了（因为hash中存储的x 是之前遍历时插入的）
                return x;
            }
            hash.insert(x);                        // 如果在hash中没有找到x，说明x还没有重复，将其插入hash
        }
    }
};

*/


// 原地交换（通过交换，先将元素放到 对应值作为下标 的位置，当遍历到除这些下标以外的地方时，会遍历到重复的元素，交换的时候会出现 要交换的元素等于该元素 的情况）
class Solution {                                
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size();) {               // 遍历数组
            if (nums[i] == i) {                           // 如果当前位置的 元素值==下标，则跳过
                ++i;
                continue;
            }
            else {                                      
                if (nums[i] != nums[nums[i]]) {           // 否则，且如果当前位置 元素值!=以该元素值为下标所指向的元素，则交换这俩个元素
                    std::swap(nums[i], nums[nums[i]]);
                }
                else {                                    // 否则，否则说明出现重复，则返回该元素
                    return nums[i];
                }
            }
        }
        
        return INT_MAX;
    }
};

#pragma once
#include<vector>

using std::vector;

// 二分查找（查找值为target的元素序列 的左右边界下标）
class Solution {
public:
    int left_binary_search(int left, int right, const vector<int>& nums, int target);          // 找左边界（nums中 值等于target的元素 的最小下标）
    int right_binary_search(int left, int right, const vector<int>& nums, int target);         // 找右边界（nums中 值等于target的元素 的最大下标）

    int search(vector<int>& nums, int target) {

        int left = left_binary_search(0, nums.size() - 1, nums, target);          
        int right = right_binary_search(0, nums.size() - 1, nums, target);

        
        return (left == -1 && right == -1 ) ? 0 : right - left + 1;           // 如果 left==-1 && right==-1 说明nums中不存在target，则返回0; 否则说明存在，则返回等于target的元素的数量 right - left + 1
    }
};

int Solution::left_binary_search(int left, int right, const vector<int>& nums, int target) {
    int ans = -1;                                   // ans初始化为-1
    while (left <= right) {                    
        int mid = left + (right - left) / 2;          

        if (nums[mid] >= target) {                  // 在 nums[mid]>=target 时，移动right; "只有"在 nums[mid]<target时，移动left。
            right = mid - 1;                        // 可以看出固定left为 左边界，不断移动right往left靠，mid也就会往left靠，最终mid会和left重合
            if (nums[mid] == target) {              // 在mid往left靠的过程中，如果 nums[mid]==target，则记录 ans==mid。
                ans = mid;                          // （不需要if虽然也行，因为最终mid与left重合，left指向元素就是target，因此ans=left
            }                                       //   但是，如果不存在target的情况，left指向元素不会是target，因此ans的指向就无意义。因此为了最终更好的判断返回，我加上了if）
        }
        else {
            left = mid + 1;
        }
    }

    return ans;
}

int Solution::right_binary_search(int left, int right, const vector<int>& nums, int target) {
    int ans = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > target) {                  // "只有"在 nums[mid]>target 时，移动right; 在 nums[mid]<=target时，移动left。
            right = mid - 1;                       // 可以看出固定right为 右边界，不断移动left往right靠，mid也就会往right靠，最终mid会和right重合
        }                                          // 在mid往left靠的过程中，如果 nums[mid]==target，则记录 ans==mid。
        else {                                     // （不需要if虽然也行，因为最终mid与right重合，right指向元素就是target，因此ans=right
            if (nums[mid] == target) {             //   但是，如果不存在target的情况，right指向元素不会是target，因此ans的指向就无意义。因此为了最终更好的判断返回，我加上了if）
                ans = mid;
            }
            left = mid + 1;
        }
    }

    return ans;
}

#pragma once
#include<vector>

using std::vector;

// 二分查找（查找右子数组的第一个元素的下标，该元素是nums数组中 第一个值和下标不相等的元素，其下标值等于 缺失的数）
class Solution {
public:
    int binary_search(int left, int right, vector<int>& nums);

    int missingNumber(vector<int>& nums) {                      // 数组nums可以划分为两部分: 左子数组 nums[i]==i; 右子数组nums[i]!=[i]
        return binary_search(0, nums.size() - 1, nums);         // 根据题意可知: 右子数组中nums[i]==i+1，因为从右子数组的第一个元素 跳过了一个数，也就是缺失的数
    }
};

int Solution::binary_search(int left, int right, vector<int>& nums) {  
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] != mid) {              // 此时mid指向 右子数组范围，right=mid-1（最终right为指向 左子数组最后一个元素的下标）
            right = mid - 1;
        }
        else {
            left = mid + 1;                  // 此时mid指向 左子数组范围，left=mid+1（最终left为指向 右子数组第一个元素的下标，也就是缺失的元素的值！）
        }
    }

    return left;
}