WXL's blog

Talk is cheap, show me your work.

0%

刷算法---2021.08

发表于 更新于 分类于 阅读次数： Valine：

从2021年8月中旬开始刷题。

本文将记录我在2021年8月中所刷过的题目，题目量不多，但是每一道保证理解透彻。

力扣26题：删除有序数组中的重复项

题目链接：点击这里

AC

首先看清楚题目，这道题目说了是一个有序的数组，那么重复的元素必定是连续的，就连续这一特点我们可以摒弃平常用的字典计数的方法或者使用set的方法，而采用更加简便的方法。

  • 思路1：双指针(时间复杂度O(n)，空间复杂度O(1))

假设两个指针p和q，p在左边，q在右边，如果nums[p]==nums[q]nums[p]==nums[q]，即两指针指向的元素值相等了，那么q指针右移一个单位，再次判断俩指针指向的值是否相等，如果还是相等，q指针继续移动；如果不相等，p指针移动一个单位，且nums[p]=nums[q]nums[p] = nums[q]。

那么何时跳出循环呢？如果q到达了nums最后一个元素，那么说明了所有的元素都遍历了一遍，那么此时p所指向的就是不重复的元素的最后一个。

将上述过程写成伪代码：

1
2
3
4
5
6
7
8
9
10
11
p=0, q=1, r=0
while q < nums.size():
    if nums[p] == nums[q]:
        q++
    else:
        p++
        nums[p] = nums[q]
return p

# 这里需要注意的是，如果直接返回p结果是错的，因为测试的方式是p在nums中所对应的元素是不访问的，
# 所以需要返回p+1

可以自行举个例子来将上述过程推演一遍：
nums = 0, 0, 1, 1, 1, 2, 2, 3, 3, 4。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int p = 0, q = 1;
        while (q < nums.size()) {
            if (nums[p] == nums[q]) {
                q++;
            }
            else {
                p++;
                nums[p] = nums[q];
            }
        }
        return p + 1;
    }
};

// 代码看起来不够简洁？将一些语句合并之后得到如下的版本：
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int p = 0, q = 1;
        for (int q = 1; q < nums.size(); q++) {
            if (nums[p] != nums[q]) 
                nums[++p] = nums[q];
        }
        return p + 1;
    }
};
  • 思路2：使用STL(时间复杂度O(n)，空间复杂度O(1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return distance(nums.begin(), 
        removeDuplicates(nums.begin(), nums.end(), nums.begin()));
    }

    template<typename  InIt, typename OutIt>
    OutIt removeDuplicates(InIt first, InIt last, OutIt output) {
        while (first != last) {
            *output++ = *first;
            first = upper_bound(first, last, *first);
        }

        return output;
    }
};
  • 思路3：通用解法，将原问题的「最多保留 1 位」修改为「最多保留 k 位」。

假设我们使用的nums=[1,1,1,2,2,3]nums=[1, 1, 1, 2, 2, 3]
我们仍然使用双指针法。这样的思路：

既然需要保留K个相同的数字，我们就用一个变量r来存储当前数字的相同的个数。一开始p指针指向index=0，q指针指向index=1，首先判断nums[p]==nums[q]nums[p]==nums[q]是否成立，如果是的，我们需要判断计数器r的值是否超出了K的限定范围，如果超出了，那么只用q继续往后走，如果没有超出，我们让与p相距r个位置的数值=nums[q]，即：nums[p+r]=nums[q]nums[p+r] = nums[q]；如果不成立，即此时nums[p]!=nums[q]nums[p]!=nums[q]，假设刚刚在遍历数字1，那么此时意味着此时数字1已经遍历完了，所以nums[q]=2nums[q]=2，这个时候我们要将p指针指向这个新的数字的开端，即p=q。

这样写有什么问题？

如果p和q之间相差很多呢，比如1， 1， 1， 1， 1， 1，2，此时p指向第三个1，而q指向2，能将p直接指向q的2吗？显然不能！但是想起来我们用了一个计数器r，这就容易想到我们可以使用计数器来实现p指针的新指向：p+=rp += r。然后是一个新的数字了，所以计数器r需要更新为1，新的数字还要移动过来给p：nums[p]=nums[q]nums[p] = nums[q]，这就是一个完整的循环需要做的事情。循环结束的标志？和K为1的时候一样，当q超出nums长度即停止。

综合上述流程的伪代码为：

1
2
3
4
5
6
7
8
9
k=2, p = 0, q = 1, r = 1
while q < nums.size():
	if nums[p] == nums[q]:
		nums[p + r] = nums[q]
		r++, q++
	else:
		p += r, r = 1
		nums[p] = nums[q]
		q++

使用C++来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int k = 2, r = 1, p = 0, q = 1;

        for (; q < nums.size(); q++) {
           if (nums[p] == nums[q]) {
               if (r < k) {
                   nums[p + r] = nums[q];
                   r++;
               }
           }
           else {
               p += r;
               r = 1;
               nums[p] = nums[q];
           }
        }
        return p + 1;
        }
};

问题来了，将这段C++代码拿去运行发现只能通过部分案例，什么问题？仔细分析代码之后发现，如果在退出循环之前，进入的是else分支，那么p将得到更新：p+=rp+=r，如果经过的是if分支，p无法得到更新，直接退出循环！所以这里逻辑需要更改，可以直接在if分支中让每一次p+r吗?不行，因为r是不断增加的。我的解决方式是，每一次都让p更新一下，而不是到了最后一次性加上r，即在每一次遇到与nums[p]相同数字的时候，如果r<k就马上更新p：

1
2
3
4
5
6
if (nums[p] == nums[q]) {
    if (r < k) {
        r++;
        nums[++p] = nums[q];
    }
}

这样就可以将else分支中的p+=r去掉：

1
2
3
4
5
else {
//  p += r;
    r = 1;
    nums[++p] = nums[q];
}

完整的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int k = 2, r = 1, p = 0, q = 1;

        for (; q < nums.size(); q++) {
           if (nums[p] == nums[q]) {
               if (r < k) {
                   r++;
                   nums[++p] = nums[q];
               }
           }
           else {
//               p += r;
               r = 1;
               nums[++p] = nums[q];
           }
        }
        return p + 1;
    }
};

这个搞定之后，可以顺便去把这道题给AC掉：
80. 删除有序数组中的重复项 II

力扣33题.搜索旋转排序数组

题目链接：点击这里

AC

这道题如果不去考虑时间复杂度的限制将是非常容易的遍历问题，但是本题的进阶方案是：设计一个时间复杂度为O(logn)O(log n)的解决方案。

想到时间复杂度为O(logn)O(logn)很容易思考到二分查找法，但是本题只是两部分有序的，所以直接用原本的二分查找行不通，需要进行修改，思路如下：

假设输入的nums=4,5,6,0,1,2,3nums={4,5,6,0,1,2,3}。

初始left=0,right=nums.size()left=0,right=nums.size()，每一次循环中，取mid=(left+right)/2mid=(left+right)/2，将序列最左端的值和target比较，有两种情况需要重点考虑：1. num[left]>targetnum[left]>target，2. num[left]<targetnum[left]<target，等于的话直接结束程序。

如果 num[left]>targetnum[left]>target，nums[mid]nums[mid]有3种情况，一种是比target大，一种是比它小，最后就是相等。

  • 如果nums[mid]>targetnums[mid]>target​，还有两种情况，一种是nums[mid]nums[mid]​在numsnums​的最小值的左边，那么此时有：nums[mid]<target<nums[right]nums[mid]<target<nums[right]​，所以更新left=midleft=mid​；一种是在numsnums​的最小值的右边，这种情况下，nums[mid]nums[mid]​和nums[right]nums[right]​均大于targettarget​，所以需要更新left=left,right=midleft=left,right=mid​。
  • 如果nums[mid]<targetnums[mid]<target，只有一种情况，更新为：left=mid,right=rightleft=mid,right=right。
  • 如果nums[mid]==targetnums[mid]==target，找到目标值。

如果 num[left]<targetnum[left]<target，midmid同样有3中情况，即nums[mid]>target,nums[mid]<target,nums[mid]==targetnums[mid]>target, nums[mid]<target, nums[mid]==target。

  • 如果nums[mid]>targetnums[mid]>target，只有一种情况，即：nums[left]<target<nums[mid]nums[left]<target<nums[mid]，更新为：left=left,right=midleft=left, right=mid
  • 如果nums[mid]<targetnums[mid]<target​​​，有两种情况，一种是nums[mid]nums[mid]​​​在numsnums​​​最小值的左边，那么此时有：nums[left]<nums[mid]<targetnums[left]<nums[mid]<target​​​，这种情况下，需要更新：left=mid,right=rightleft=mid,right=right​​​；另一种是nums[mid]nums[mid]​​​在numsnums​​​最小值的右边，此时有：nums[left]<target<nums[mid]<nums[right]nums[left]<target<nums[mid]<nums[right]​​​，所以更新left=left，right=midleft=left，right=mid​​​。
  • 如果nums[mid]==targetnums[mid]==target​，找到目标值。

将上述思路使用代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (nums[left] > target)
            {
                if (nums[mid] > target)
                {
                    if (nums[mid] >= nums[left]) // mid在最小值的左边
                        left = mid;
                    else                         // mid在最小值的右边
                        right = mid;
                }
                else if (nums[mid] < target)
                    left = mid;
                else
                    return mid;
            }
            else if (nums[left] < target)
            {
                if (nums[mid] > target)
                    right = mid;
                else if(nums[mid] < target)
                {
                    if (nums[mid] >= nums[left])  // mid在最小值的左边
                        left = mid;
                    else                          // mid在最小值的右边
                        right = mid;
                }
                else
                    return mid;
            }
            else
                return left;
        }
        return -1;
    }
};

这段代码并不能通过所有的实例，准确的说，很多实例都无法通过，一旦进入类似这样的情况：[2,3]，left=0,right=1,target=4[2, 3]，left=0, right=1,target=4​，这种情况下，取mid=(0+1)/2mid=(0+1)/2，取整，得到mid=0mid=0，就会一直循环下去。

其实在二分法中，仅仅使用左右区间索引值之和的一半很容易出现这种循环，需要走出循环，一定需要通过加减来变化索引的值

比如我知道了nums[mid]<targetnums[mid]<target​，就取left=mid+1left=mid+1​，而不是left=midleft=mid。通过加减1走出循环将上述代码改为如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (nums[left] > target)
            {
                if (nums[mid] > target)
                {
                    if (nums[mid] >= nums[left]) // mid在最小值的左边
                        left = mid + 1;
                    else                         // mid在最小值的右边
                        right = mid - 1;
                }
                else if (nums[mid] < target)
                    left = mid + 1;
                else
                    return mid;
            }
            else if (nums[left] < target)
            {
                if (nums[mid] > target)
                    right = mid - 1;
                else if(nums[mid] < target)
                {
                    if (nums[mid] >= nums[left])  // mid在最小值的左边
                        left = mid + 1;
                    else                          // mid在最小值的右边
                        right = mid - 1;
                }
                else
                    return mid;
            }
            else
                return left;
        }
        return -1;
    }
};
行行好，赏一杯咖啡吧~