剑指offer 03. 数组中重复的数字 (easy)


#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;
    }
};
官方题解:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-b-4/
优质题解:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-yua/

剑指offer 53 - I. 在排序数组中查找数字 (easy)


#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;
}

剑指offer 53 - II. 0~n-1中缺失的数字 (easy)


#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;
}
优质题解:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/