当前位置：首页 > article >正文

【LeetCode刷题记录】数组专题

article 2024/9/24 14:29:22

说明：

文章内容为个人的力扣刷题记录，不定时更新。
文章内容如有错误，欢迎指正。

文章目录

- - 2023-04-24 题目1. 两数之和
  - - 方法一：暴力解法，循环遍历
    - 方法二：哈希表
  - 2023-04-25 4. 寻找两个正序数组的中位数
  - - 方法一：双指针法+使用额外空间
    - 方法二：双指针法+不使用额外空间
  - 2023-4-27 11. 盛水最多的容器
  - 2023-4-27 15.三数之和
  - 2023-4-28 16. 最接近的三数之和
  - 2023-4-29 18.四数之和
  - 2023-4-30 26. 删除有序数组中的重复项
  - 2023-5-1 27.移除元素
  - - 方法一：排序+查找
    - 方法二：双指针（快慢指针）
  - 2023-5-2 31.下一个排列
  - 2023-5-3 33. 搜索旋转排序数组
  - - 方法一：“二分查找”
    - 方法二：先找边界值再二分查找
  - 2023-5-4 34. 在排序数组中查找元素的第一个和最后一个位置
  - - 方法一：二分查找+单步移动指针
    - 方法二：两次二分查找
  - 2023-5-5 35. 搜索插入位置

2023-04-24 题目1. 两数之和

1. 两数之和 - 力扣（Leetcode）

方法一：暴力解法，循环遍历

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0; i<nums.size()-1; i++){
            for(int j=i+1; j<nums.size(); j++){
                if(nums[i]+nums[j] == target){
                    return {i,j};
                }
            }
        }      
        return {};  
    }
};

python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 方法一：暴力解法：循环遍历
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    return [i,j]
        return []

方法二：哈希表

参考1. 两数之和 - 力扣（Leetcode）

哈希表的查找时间复杂度为O(1)，可以大大降低时间复杂度
算法思想：
- 构建哈希表hashTable
- 遍历nums，每遍历到一个值nums[i]，就判断hashTable中是否存在key为target-nums[i]的元素
- 若存在，则找到这两个元素，并返回下标；若不存在，则将(nums[i],i)作为(key,value)存入哈希表中，继续遍历直至找到
- 若最后没有找到则返回空
C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {        
        //方法二：哈希表
        //利用C++ STL中的unordered_map数据结构构造哈希表
        unordered_map<int,int> hashTable;
        for(int i=0; i<nums.size(); i++){
            auto iter = hashTable.find(target-nums[i]); //返回的是一个迭代器
            //如果找到则返回key为target-nums[i]的迭代器
            //找不到就返回尾后迭代器
            if(iter != hashTable.end()){
                return {iter->second, i}; //iter->second即元素下标
            }
            //没有找到，将(nums[i],i)作为(key,value)存入哈希表
            hashTable.insert(pair<int,int>(nums[i], i));
        }
        return {};
    }
};

python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 方法二：哈希表 python3
        # 利用Python的字典数据结构构造哈希表
        hashTable = dict()
        for i in range(len(nums)):
            if target-nums[i] in hashTable: # 在python2中使用的是has_key()函数判断
                return [hashTable.get(target-nums[i]), i]
            hashTable[nums[i]] = i
        
        return []

2023-04-25 4. 寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数 - 力扣（Leetcode）
都是升序数组，且要求时间复杂度为O(m+n)，使用双指针法。

方法一：双指针法+使用额外空间

将两个数组合并为一个升序数组，在这个新数组中寻找中位数，空间复杂度为O(m+n)。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 双指针法
		// 方法一：使用额外空间,空间复杂度为O(m+n)       
        int m=nums1.size(), n=nums2.size();
        vector<int> merge;
        int i=0, j=0; // 双指针
        
        // 建立新的升序数组
        while(i<m || j<n){
            if(i<m && j<n){ 
                if(nums1[i] < nums2[j]) merge.push_back(nums1[i]), i++;
                else if(nums2[j] < nums1[i]) merge.push_back(nums2[j]), j++;
                else merge.push_back(nums1[i]), merge.push_back(nums2[j]), i++, j++;
            }else{ // 如果有一个指针越界，则后移另一个
                if(i >= m && j < n) merge.push_back(nums2[j]), j++;
                if(j >= n && i < m) merge.push_back(nums1[i]), i++;
            }
        }
  
        // 寻找中位数
        if((m+n)%2 == 0){
            return (float)(merge[(m+n)/2 - 1] + merge[(m+n)/2])/2;
        }else{
            return (float)merge[(m+n)/2];
        }
};

python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 使用额外空间
        m,n = len(nums1), len(nums2)
        merge = []
        i = 0
        j = 0

        # 建立新的升序数组
        while i<m or j<n :
            if i<m and j<n:
                if nums1[i] < nums2[j]: 
                    merge.append(nums1[i])
                    i += 1
                elif nums2[j] < nums1[i]:
                    merge.append(nums2[j])
                    j += 1
                else:
                    merge.append(nums1[i])
                    merge.append(nums2[j])
                    i += 1
                    j += 1
            else: # 两个指针有一个越界
                if i >= m and j < n: 
                    merge.append(nums2[j])
                    j += 1
                if j >= n and i < m:
                    merge.append(nums1[i])
                    i += 1

        # 寻找中位数     
        if (m+n)%2 == 0:
            return float((merge[(m+n)//2 - 1] + merge[(m+n)//2])/2)
        else:
            return float(merge[(m+n)//2])

方法二：双指针法+不使用额外空间

通过上面的的“使用额外空间”的方法，可以看到，最后有用的是最中间的一个值（或最中间的两个值），那么可以在遍历的过程中只保存中间的值，最后只利用最中间的值。

算法思想：

设置两个变量pre，cur来模仿将数值插入新数组的过程。pre保存上一个插入数组的值，cur保存当前插入数组的值；
变量mid_iter保存遍历的次数，当遍历次数达到(m+n)/2时，结束循环，此时说明我们已找到中位数；
如果m+n为偶数，中位数就是最中间的两个值，返回(pre+cur)/2；如果m+n为基数，中位数就是最中间的一个值，返回cur。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 不使用额外空间
        int m=nums1.size(), n=nums2.size();
        int i=0, j =0;
        int mid_iter = 0; // 保存循环的次数
        int pre=-1, cur=-1; 

        // 遍历寻找中位数
        while(mid_iter <= (m+n)/2){
            if(i<m && j<n){
                if(nums1[i] < nums2[j]){
                    pre = cur, cur = nums1[i];
                    i++, mid_iter++;
                } else if(nums2[j] < nums1[i]){
                    pre = cur, cur = nums2[j];
                    j++, mid_iter++;
                } else{
                    // 当两个值相等时，并不同时后移两个指针
                    // 而是模拟将一个值插入新数组，并后移该指针
                    pre = cur, cur = nums1[i];
                    i++, mid_iter++; 
                }
            } else {
                if(i >= m && j < n){
                    pre = cur, cur = nums2[j];
                    j++, mid_iter++;
                }
                if(j >= n && i < m){
                    pre = cur, cur = nums1[i];
                    i++, mid_iter++;
                }
            }
        }

        // 返回中位数
        if((m+n)%2 == 0){
            return (float)(pre+cur)/2;
        }else{
            return (float)cur;
        }
    }
};

python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m,n = len(nums1), len(nums2)
        i, j = 0, 0
        mid_iter = 0
        pre, cur = -1, -1

        while mid_iter <= (m+n)//2:
            if i<m and j<n:
                if nums1[i] < nums2[j]:
                    pre = cur; cur = nums1[i]
                    i += 1; mid_iter += 1
                elif nums2[j] < nums1[i]:
                    pre = cur; cur = nums2[j]
                    j += 1; mid_iter += 1
                else:
                    pre = cur; cur = nums1[i]
                    i += 1; mid_iter += 1
            else:
                if i >= m and j < n:
                    pre = cur; cur = nums2[j]
                    j += 1; mid_iter +=1
                if j >= n and i < m:
                    pre = cur; cur = nums1[i]
                    i += 1; mid_iter +=1
        
        if (m+n)%2 == 0:
            return float((pre+cur)/2)
        else:
            return float(cur)

说明：关于当两个值相等时，为什么不同时更新pre和cur，并同时后移两个指针？这是因为防止更新过快，而导致我们“跟丢”中位数，考虑下面这种情况：
如下图所示的两个数组，中位数应该是（6+9)/2=7.5，也就是说mid_iter>6的时候就应该结束循环。但是如果我们同时更新pre和cur，并同时后移两个指针，就会出现这种情况：
在这里插入图片描述

比较5<6，此时更新pre=4，cur=5，执行i++，mid_iter++，此时nums1[i]=6,nums2[j]=6;
判断mid_iter，此时mid_iter=4，继续循环。比较6==6, 此时同时更新pre=6,cur=6，执行i++, j++,mid_iter+=2，此时nums1[i]=9, nums2[j]=9;
判断mid_iter，此时mid_iter=6，继续循环。比较9==9，此时同时更新pre=9,cur=9，执行i++,j++,mid_iter+=2，此时nums1[i]=11,nums2[j]=12;
判断mid_iter，此时mid_iter=8，结束循环

但这时候计算出的中位数就是(9+9)/2=9，而不是7.5。这就是更新太快，导致中位数被跟丢了。按理说当mid_iter=7的时候就应该结束循环，但由于同步更新的策略，导致我们错过了中位数。

如果采用单步更新策略，那么执行过程就是：

比较5<6，此时更新pre=4，cur=5，执行i++，mid_iter++，此时nums1[i]=6,nums2[j]=6;
判断mid_iter，此时mid_iter=4，继续循环。比较6==6, 此时更新pre=5,cur=6，执行i++,mid_iter++，此时nums1[i]=9, nums2[j]=6;
判断mid_iter，此时mid_iter=5，继续循环。比较6<9，此时更新pre=6,cur=6，执行j++,mid_iter++，此时nums1[i]=9,nums2[j]=9;
判断mid_iter，此时mid_iter=6，继续循环。比较9==9，此时更新pre=6,cur=9，执行i++,mid_iter++，此时nums1[i]=11,nums2[j]=9;
判断mid_iter，此时mid_iter=7，结束循环。

此时计算结果就是7.5。单步更新策略，就不会由于更新过快导致中位数被跟丢。

有位大佬写了解法三和解法四，利用了二分查找的思想，可以将时间复杂度降为log级别，参考https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/8999/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

2023-4-27 11. 盛水最多的容器

11. 盛水最多的容器
首先想到的是暴力解法，嵌套循环寻找最大值，但是暴力解法超时了。

思考如何优化，优化的思路就是减少一层循环。可以采用双指针法，一个指针从前向后移动，另一个指针从后向前移动，并记录移动过程中的最大水量，这样就可减少一层循环，降低时间复杂度。

接下来的关键是如何确定指针的移动规则。假设两个指针分别为i（从前向后移动），j（从后向前），我们可以得出每次的容器盛水量为 $volume = min\{height[i], height[j]\}*(j-i)$ 。可以发现，每次无论移动的是 i 还是 j ， $(j - i)$ 都会减少一，为了得到最大盛水量，我们应想法设法让 $min\{height[i], height[j]\}$ 增大，也就是说让指向更小值的那个指针移动，这样才有机会得到更大的height，才有可能使 $min\{height[i], height[j]\}$ 增大。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i=0, j=height.size()-1; // 双指针
        int min_h = 0; 
        int max_v = 0; // 最大盛水量
        int volume = 0; // 计算每次的盛水量

        while(i != j){ // 两个指针相遇，结束循环
            min_h = height[i] <= height[j] ? height[i] : height[j]; 
            volume = min_h * (j - i);
            if(volume > max_v) max_v = volume; // 更新最大盛水量
            // 移动指针
            if(height[i] <= height[j]) i++;
            else j--;
        }

        return max_v;
    }
};

python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j = 0, len(height)-1
        max_v = 0

        while i != j:
            min_h = height[i] if height[i] <= height[j] else height[j]
            volume = min_h * (j - i)
            if volume > max_v: max_v = volume # 更新最大盛水量
            # 移动指针
            if height[i] <= height[j]: i += 1
            else: j -= 1
        
        return max_v

2023-4-27 15.三数之和

15.三数之和
最容易想到的是暴力解法，但是暴力解法会超时。从暴力解法中思考如何优化，能不能减少循环嵌套的层数。在暴力解法的最内层循环中，我们是固定指针i，j，移动指针k来寻找结果，能不能每次只固定一个指针，然后移动另外两个指针，这样就能减少一层循环。这就需要利用排序。

首先对数组进行排序，得到一个升序数组。
设置三个指针i, front, rear，i从前向后移动，front从i+1向后移动，rear从nums.size()-1向前移动，front和rear相向而行，寻找结果，相遇即停。
当三数之和sum等于0时，则找到一个结果，并更新front和rear；当sum小于0，则front++；当sum大于0，则rear–
对结果进行去重

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> results;

        sort(nums.begin(), nums.end());
        int front = 0, rear = 0; // 两个前后指针
        for(int i=0; i<nums.size()-2; i++){
            if(nums[i] > 0) break; // 此时说明后续全是正数，无需再循环
            if(i > 0 && nums[i] == nums[i - 1]) continue; // 这一步是为了去重
            front = i + 1;
            rear = nums.size()-1;
            while(front < rear){
                int sum = nums[i] + nums[front] + nums[rear];
                if(sum == 0){
                    vector<int> temp{nums[i], nums[front], nums[rear]};
                    sort(temp.begin(), temp.end()); // 便于后续results去重
                    results.push_back(temp);
                    front++;
                    rear--;
                }else if(sum < 0){
                    front++;
                }else{
                    rear--;
                }
            }
        }
        // results去重      
        results.erase(unique(results.begin(), results.end()), results.end());

        return results;
    }
};

上述代码运行时间约为124ms，二次去重的时候results.erase(unique(results.begin(), results.end()), results.end());这条语句会比较耗时，可以将二次去重写在循环体内，二次去重去的是重复的nums[front]和nums[rear]。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> results;

        sort(nums.begin(), nums.end());
        int front = 0, rear = 0; // 两个前后指针
        for(int i=0; i<nums.size()-2; i++){
            if(nums[i] > 0) break; // 此时说明后续全是正数，无需再循环
            if(i > 0 && nums[i] == nums[i - 1]) continue; // 这一步是为了去重
            front = i + 1;
            rear = nums.size()-1;
            while(front < rear){
                int sum = nums[i] + nums[front] + nums[rear];
                if(sum == 0){
                    vector<int> temp{nums[i], nums[front], nums[rear]};
                    sort(temp.begin(), temp.end()); // 便于后续results去重
                    results.push_back(temp);

                    // 可以在这里写results的二次去重
                    while(front<rear && nums[front]==nums[front+1]) front++;
                    while(front<rear && nums[rear]==nums[rear-1]) rear--;

                    front++;
                    rear--;
                }else if(sum < 0){
                    front++;
                }else{
                    rear--;
                }                
            }
        }
        // // results去重
        // results.erase(unique(results.begin(), results.end()), results.end());

        return results;
    }
};

这样运行时间会减少至96ms。

2023-4-28 16. 最接近的三数之和

16. 最接近的三数之和
这道题和15题三数之和很像，两道题的解题思路也大同小异。
算法思想：

对数组进行排序；
设置三个指针i, front, rear，i从前向后移动，front从i+1向后移动，rear从nums.size()-1向前移动，front和rear相向而行，寻找结果，相遇即停；
当三数之和sum等于target时，直接返回；
若sum和target的差距比sim_sim（最接近的三数之和）与target的差距更小，则更新sim_sum的值，同时更新指针。当sum>target时，rear–；当sum<target时，front++。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // 双指针法
        sort(nums.begin(), nums.end()); // 排序
        int front=0, rear=0;
        int sum = 0; // 每次求和的值
        int sim_sum = 65535; // 存放与target最接近的和值

        for(int i=0; i<nums.size()-2; i++){            
            front = i + 1;
            rear = nums.size() - 1;   
            while(front < rear){
                sum = nums[i] + nums[front] + nums[rear];
                if(sum == target) return sum; // 直接返回
                // 更新最接近的和值
                if(abs(target-sum) < abs(target-sim_sum)) sim_sum = sum;                                      
                // 更新指针
                if(sum > target) rear--;
                else front++;
            }            
        }

        return sim_sum;
    }
};

python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        sum_ = 0
        sim_sum = 65535

        for i in range(len(nums)-2):
            front = i + 1
            rear = len(nums) - 1
            while front < rear:
                sum_ = nums[i] + nums[front] + nums[rear]
                if sum_ == target: return sum_
                # 更新最接近的和值
                if abs(target-sum_) < abs(target-sim_sum): sim_sum = sum_
                # 更新指针
                if sum_ > target: rear -= 1
                else: front += 1
        
        return sim_sum

但是用python这样写运行很慢，大概856ms。后来我试着把调用绝对值函数改为三目表达式，运行时间降为752ms，调函数缺失会耗费一些时间，但改完也没提升多少。

2023-4-29 18.四数之和

18.四数之和
求四数之和的解题思路和求三数之和的解题思路基本上是一样的。在求三数之和时，是通过每次固定指针i，移动指针front和rear来找到结果，从而将时间复杂度降为 $O(n^2)$ 。那么求四数之和时，每次固定两个指针i，j，移动指针front和rear来找到结果。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // 双循环+双指针
        vector<vector<int>> results;
        int front=0, rear=0;
        if(nums.size() < 4) return results;
        
        sort(nums.begin(), nums.end());        

        for(int i=0; i<nums.size()-3; i++){
            if(i>0 && nums[i]==nums[i-1]) continue; // 去重
            for(int j=i+1; j<nums.size()-2; j++){
                if(j>i+1 && nums[j]==nums[j-1]) continue; //去重
                front = j + 1;
                rear = nums.size()-1;
                while(front < rear){
                    // 多个int型数值相加可能会溢出
                    long long sum = (long long)nums[i] + nums[j] + nums[front] + nums[rear];
                    if(sum > target){
                        rear--;
                    } else if(sum < target){
                        front++;
                    }else {
                        results.push_back(vector<int>{nums[i], nums[j], nums[front], nums[rear]});
                        // 去重
                        while(front<rear && nums[front]==nums[front+1]) front++;
                        while(front<rear && nums[rear]==nums[rear-1]) rear--;
                        // 更新双指针
                        front++, rear--;
                    }  
                }
            }
        }

        return results;
    }
};

然后我发现个事情，我最开始的版本的if-else顺序是if(sum==target)在最前面，这一版本的运行时间是92ms，然后我修改了if-else语句的顺序，把(sum==target)判断成功的语句写在了最后面，运行时间是68ms。这可能跟测试样例有关吧？

python

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        results = []
        length = len(nums)
        if length < 4 : return results

        nums.sort()
        for i in range(length-3):
            if i>0 and nums[i]==nums[i-1] : continue # 去重
            for j in range(i+1,length-2):
                if j>i+1 and nums[j]==nums[j-1]: continue # 去重
                
                front, rear = j+1, length-1
                while front < rear:
                    sum_num = nums[i] + nums[j] + nums[front] + nums[rear]
                    if sum_num < target: front += 1
                    elif sum_num >  target: rear -= 1
                    else:
                        results.append([nums[i], nums[j], nums[front], nums[rear]])
                        while front<rear and nums[front]==nums[front+1]: front += 1 # 去重
                        while front<rear and nums[rear]==nums[rear-1]: rear -= 1 # 去重
                        # 更新指针
                        front += 1
                        rear -= 1
        
        return results

2023-4-30 26. 删除有序数组中的重复项

26. 删除有序数组中的重复项
题目已经指出数组是升序的，那么利用升序这一条件，设置两个指针，来删除重复项。

算法思路：

设置两个指针i，j，初始时i=0,j=1。当j<nums.size()时开始循环遍历；
每次判断nums[i]和nums[j]是否相等，若相等则j++向后移动j指针；当nums[i]和nums[j]不相等时，则令nums[i+1]=nums[j]，并更新i，j指针，即i++，j++。
最后返回i+1，即数组中唯一项的个数。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i=0, j=1;
        while(j < nums.size()){
            while(j < nums.size() && nums[i] == nums[j]) j++;
            if(j < nums.size()) nums[++i] = nums[j++];            
        }
        
        return i+1;
    }
};

python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i, j = 0, 1
        while j < len(nums):
            while j < len(nums) and nums[i] == nums[j]: j += 1
            if j < len(nums): 
                nums[i+1] = nums[j]
                i += 1
                j += 1
        
        return i+1

注：刚开始写时，在更新nums[i],nums[j]和i，j指针时会忘记判断j < nums.size()，会导致结果出错，要注意这条判断语句不能少，因为在前面会循环更新j指针，在更新过程中可能会导致j指针溢出，因此在更新数值和指针之前要先判断一下。

2023-5-1 27.移除元素

27.移除元素
明天要出去玩，提前把明天要写的题写了。

方法一：排序+查找

将数组排序后得到一个有序数组，之后再用二分查找寻找值等于val的元素。因为数组有序，因此若存在值等于val的元素的话，它们也是聚集在一起的，可以将其集中删除。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 排序 + 删除
        if(nums.size() == 0) return 0;
        sort(nums.begin(), nums.end());
        if(val<nums[0] || val>nums[nums.size()-1]) return nums.size();
        // 二分查找等于val的值
        int low=0, high=nums.size()-1;
        int mid;
        while(low <= high){
            mid = (low + high)/2;
            cout<<nums[mid]<<endl;
            if(nums[mid] == val) break;
            else if(nums[mid] < val) low = mid + 1;
            else high = mid - 1;
        }

        if(nums[mid] == val){ // 存在值等于val的元素
            while(mid >= 0 && nums[mid] == val) mid--;// 找到第一个值等于val的元素下标
            mid++;
            while(mid < nums.size() && nums[mid] == val) nums.erase(nums.begin()+mid);            
        } 
        return nums.size();
    }
};

方法二：双指针（快慢指针）

在方法一中是直接删除元素，也可以采用覆盖的方式，修改数组中的元素。
定义两个指针，分别为slowIndex, fastIndex。其中fastIndex用来寻找新数组的元素，新数组是不包含val的；slowIndex用来指向新数组下标位置。

当nums[fastIndex] != val时，更新nums[slowIndex]为nums[fastIndex]，并同时将快慢指针后移；
当nums[fastIndex] == val时，此时不能更新nums[slowIndex]，只用将快指针fastIndex后移即可。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size()==0)
            return 0;
        int slowIndex = 0;
        for(int fastIndex=0; fastIndex < nums.size(); fastIndex++){
            if(nums[fastIndex] != val){
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

2023-5-2 31.下一个排列

31.下一个排列
这是一道字典序算法的题目。字典序算法的讲解可参考这篇文章：字典序算法详解

算法步骤：

在数组中从右向左寻找第一个左>右的元素，记录其数值first_num和下标num_index;
继续在原数组中从右向左寻找第一个大于first_num的元素，记录其数值first_bigger和下标bigger_index；
交换数组中这两个元素的值；
将数组中num_index之后的元素从小到大排列。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int first_num=0, first_bigger=0;
        int num_index=0, bigger_index=0;
        // 从右向左找第一个左<右的元素
        for(int i=nums.size()-1; i>0; i--){
            if(i>0 && nums[i-1]<nums[i]){
                first_num = nums[i-1];
                num_index = i-1;
                break;
            }
        }
        // 从右向左找第一个大于刚刚找到的first_num
        for(int i=nums.size()-1; i>num_index; i--){
            if(nums[i] > first_num){
                first_bigger = nums[i];
                bigger_index = i;
                break;
            }
        }
        // 交换first_num和first_bigger的值
        swap(nums[num_index], nums[bigger_index]);
        // 将num_index之后的元素从小到大排列
        sort(nums.begin()+num_index+1, nums.end());

        return ;
    }
};

2023-5-3 33. 搜索旋转排序数组

33. 搜索旋转排序数组

方法一：“二分查找”

看到题目要求时间复杂度为O(logn)，首先想到二分查找，但是这个题目中的数据并不是全局有序的，如何利用二分查找的特性？

可以看到旋转后的数据其实是两段有序区间：左区间和右区间，我们要做的就是在这两个区间内寻找target。那么首先应该确定target位于哪个区间内，然后再在该区间内寻找target。
算法思路：

和传统的二分查找一样，设置left,right,mid，mid每次指向中间值；
当nums[mid]等于target时，返回下标；否则，判断此时mid指向的是左区间还是右区间
- 若mid指向左区间，接下来要判断是往左走还是往右走。若要往左，说明target位于left和mid之间；当target位于左区间的右半段或是位于右区间内，此时应往右走
- 若mid指向右区间，接下来要判断是往左走还是往右走。若要往右，说明target位于mid和right之间；当target位于右区间的左半段或是位于左区间内，此时要往左走。
如果没有找到，返回-1.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 二分查找
        int left=0, right=nums.size()-1, mid;
        while(left <= right) {
            mid = (left+right)/2;
            if(nums[mid] == target) return mid;
            // 判断mid指向左区间还是右区间
            else if(nums[left] <= nums[mid]) { // mid指向左区间
                // 接下来判断是往左走还是往右走
                // 若要往左，说明target夹在left和mid之间
                if(nums[mid]>target && nums[left]<=target) right = mid - 1;
                // 剩下的情况就是往右。往右又分为两种
                // target位于左区间的右半段;target位于右区间内
                else if(nums[mid] < target || nums[left] > target) left = mid + 1;
            }else{ // 默认另一种情况就是指向右区间
                // 接下来判断是往左走还是往右走
                // 若要往右，说明target夹在mid和right之间
                if(nums[mid]<target && nums[right]>= target) left = mid + 1;
                // 剩下的情况就是往左。往左又分为两种
                // target位于右区间的左半段；target位于左区间内
                else if(nums[mid]>target || nums[right]<target) right = mid - 1;
            }            
        }
        return -1;
    }
};

这段代码在力扣上的运行时间为8ms。在确定mid指向哪个区间之后，我们要决定往左还是往右，以mid指向左区间为例，如果target夹在left和mid之间就往左，之后又分为两种情况来判断往右走，但其实剩余的情况就是往右走，此时直接else即可。修改后的代码如下，这段代码在力扣上的执行时间为4ms：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 二分查找
        int left=0, right=nums.size()-1, mid;
        while(left <= right) {
            mid = (left+right)/2;
            cout<<nums[mid]<<endl;
            if(nums[mid] == target) return mid;
            // 判断mid指向左区间还是右区间
            if(nums[left] <= nums[mid]) { // mid指向左区间
                // 接下来判断是往左走还是往右走
                // 若要往左，说明target夹在left和mid之间
                if(nums[mid]>target && nums[left]<=target) right = mid - 1;
                // 剩下的情况就是往右。往右又分为两种
                // target位于左区间的右半段;target位于右区间内
                // else if(nums[mid] < target || nums[left] > target) left = mid + 1;
                else left = mid + 1;
            }else{ // 默认另一种情况就是指向右区间
                // 接下来判断是往左走还是往右走
                // 若要往右，说明target夹在mid和right之间
                if(nums[mid]<target && nums[right]>= target) left = mid + 1;
                // 剩下的情况就是往左。往左又分为两种
                // target位于右区间的左半段；target位于左区间内
                // else if(nums[mid]>target || nums[right]<target) right = mid - 1;
                else right = mid - 1;
            }            
        }
        return -1;
    }
};

方法二：先找边界值再二分查找

在方法一中，我们每次只能知道mid位于哪个区间内，通过移动左右边界指针（left，right）来逐渐缩小所界定的区间，但并不知道左右两个区间的界限在哪里。方法二的思想是，先找到左右区间的界限，然后准确确定在哪个区间内进行查找，确定区间之后，再进行二分查找。
算法思路：

先寻找左右区间的界限boarder（boarder为下标）；
比较target和界限值以及数组的端点值，来确定之后在哪个区间内进行查找；
确定区间之后，在该区间内进行二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left,right,mid;
        int boarder = max_element(nums.begin(), nums.end()) - nums.begin();
        cout<<boarder<<endl;
        if(target > nums[boarder]) return -1;
        if(nums[0]<=target && target<=nums[boarder]){
            left = 0;
            right = boarder;
        }
        if(boarder<nums.size()-1 && nums[boarder+1]<=target && target<=nums[nums.size()-1]){
            left = boarder+1;
            right = nums.size()-1;
        }
        while(left <= right){
            mid = (left+right)/2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid -1;
            else left = mid + 1;
        }

        return -1;
    }
};

这个方法好像更快一些，在力扣上的运行时间为0ms。但是这个方法就偷懒调用了max_element函数，之前试着自己用if-else来寻找区间界限，但是if-else执行起来很慢，于是乎直接调用了现成的函数。

2023-5-4 34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置
数组单调不减且要求时间复杂度为O(logn)，首选二分查找。

方法一：二分查找+单步移动指针

算法思路：二分查找到target之后，单步移动指针，找到target出现的位置。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=0, right=nums.size()-1, mid;
        vector<int> results;
        while(left <= right){
            mid = (left+right)/2;
            if(nums[mid] == target){
                int temp = mid;
                while(mid>=0 && nums[mid]==target) mid--;
                while(temp<=nums.size()-1 && nums[temp]==target) temp++;
                results.push_back(mid+1);
                results.push_back(temp-1);
                return results;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        } 
        return {-1,-1};
    }
};

运行时间为8ms。

方法二：两次二分查找

算法思路：进行两次二分查找，第一次寻找target的左边界，第二次寻找target+1的左边界。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = searchBoarder(nums, target);
        int right = searchBoarder(nums, target+1) - 1;
        if(left==nums.size() || nums[left]!=target) return {-1,-1};
        return {left, right};
    }

    int searchBoarder(vector<int>& nums, int target){
        int left=0, right=nums.size()-1, mid;
        while(left <= right){
            mid = (left+right)/2;
            if(nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
};

运行时间为4ms。

2023-5-5 35. 搜索插入位置

35. 搜索插入位置
二分查找

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0, right=nums.size()-1, mid;
        while(left <= right){
            mid = (left+right)/2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return right + 1;
    }
};