落风的风
0%

leetcode数组（简单04）

Posted on In

11/19 LeetCode数组，都是爷做不出来的好题。

27 移除元素

26 删除排序数组种的重复项

80 删除排序数组中的重复项 II

6到飞起的题解：双指针之同向指针

#27 移除元素

这题做了很久还是花式报错、想要用条件语句来处理很多种的特殊情况是不太合理的。程序要想极致精简、一个具有泛性能力的思路是必要的。也就是说如果最后陷入调试的怪圈，还不如推倒重来，想想看是不是思路本身就存在着一些问题。

这一题的思路其实应该算是逻辑可以自达的，想要移出指定元素，无非两种：第一，将要移出的元素一个一个的置后；或者第二，将要保留的元素分别置前。

我自己想的是将移出元素置后，这里有一个问题就是当置换回来的元素仍然是“要扔”的元素时、迭代不应该进入下一步、应该回来继续判断继续迭代，这里题解给的小技巧是while循环不用i++、用在for循环里面应该自己设置一个i–；很有智商了这个。

第二种方法是将需要的元素置前，不需要的就跳过，循环遍历直至数组尾部，输出结果为置换的次数。

解答一：需要元素前置

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
        int count = 0;
        int length = nums.length;
        for (int j = 0 ; j<=length-1;j++){
            if (nums[j]!=val){
                nums[count]=nums[j];
                count++;
            }
        }
        return count;
    }
}

解答二：不需要元素后移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeElement(int[] nums, int val) {
        int count = 0 ;
        int i = 0;
        int length = nums.length;
        while(i<=length-1-count){
            if (nums[i]==val){
                nums[i]=nums[length-1-count];
                count++;
            }else{
                i++;
            }
        }
        return length-count;
    }
}

解答三：不需要元素后移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeElement(int[] nums, int val) {
        int count= 0;
        int length = nums.length;
        for (int i=0;i<=length-1-count;i++){
            if (nums[i]==val){
                nums[i]=nums[length-1-count];
                i--; //为防止换到前面的元素仍然是val，所以此处索引需要重新判断
                count++;
            }
        }
        return length-count;
    }
}

# 26 删除排序数组种的重复项

双指针的威力是“无穷的”，只要你想就可以把指针定位到任何地方，双指针就是平等的两个指针、不要总是拘泥于单个指针的前后几位，两个指针相互之间的访问、赋值是其便利之处。

就是想像评论里面感叹一样：“看人这思路、我像弱智。”

解答：双指针方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        if (length == 0){
            return 0;
        }
        int i = 0;
        for (int j = 1; j<=length-1;j++){
            if (nums[j]!=nums[i]){
                nums[i+1]=nums[j];
                i++;
            }
        }
        return i+1;
    }
}

# 80 删除排序数组中的重复项 II

没做出来、边界条件搞不清楚。

官方解答一：

简单来说还是用双指针、一个指针 i 遍历、一个指针j指向目标数组的结尾，然后还要加上一个记住数字出现次数的count，用来判断是否出现大于2次。

起始条件、迭代过程、终止条件见代码吧、反正背也背不下来、思路最重要，清晰的思路是能开始编程的决定性的条件。

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(int[] nums) {
        if (nums.length<=2){
            return nums.length;
        }
        int j=1;
        int count =1;
        for (int i=1;i< nums.length;i++){
            if (nums[i]==nums[i-1]){
                count++;
                if (count<=2){
                    nums[j]=nums[i];
                    j++;
                }
            }else {
                count = 1;
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

官方解答二：

这个解答略笨一点，循环记录元素重复的次数，如果次数大于2就删除此索引下的元素，要写一个删除数组指定索引元素的方法。众所周知、删除数组中的元素代价是巨大的、特别是删除数组头部的数据的时候。

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
class Solution {
    public int removeDuplicates(int[] nums) {
        int i=1, count=1, length =nums.length;
        while(i<length){
            if (nums[i]==nums[i-1]) {
                count++;
                if (count > 2) {
                    nums = remElement(nums, i);
                    length--;
                    i--;
                }
            }else {
                count = 1;

            }
            i++;

        }
        return length;
    }


    public static int[] remElement(int[] arr, int index){
        for (int i= index+1;i<=arr.length-1;i++){
            arr[i-1]=arr[i];
        }
        return arr;
    }

}

# 题解：双指针之同向指针

最近在练习双指针的题型。双指针有很多种体现，个人认为它应该是LeetCode上考点最多的题了。这题是我整理的双指针中的一类题型，我称之为同向指针。
类似的题还有: 26 删除排序数组中的重复元素、27 移除元素、快排、归并、以及这边的这题（80）。
另外像快慢指针，滑动窗口其实也是同向指针，后续打算单独做总结，这里只看上面这一类题:他们的通性是:同向指针，且其中一个指针是做循环使用的。

同向指针

同向指针很好理解，两个指针是相同方向的，类似于快慢指针求中点之类的。但不知道大家有没有这种感觉:思路很简单，写对却很难。各种条件稍有不慎全军覆没，感觉处处是坑，以至于内心写双指针是奔溃的，就跟之前写二分一样。
好了，说了那么多直接祭出神器吧！

循环不变量

简单来说,循环不变量指的是在写循环代码时，变量的值会随着循环的进行而变化，但变量的定义是必须保持不变的。
这玩意儿有什么好处呢？有的，他能帮你提高写代码的正确率！！！这里涉及到一个数学推理。

在使用循环的算法里，可以通过循环不变量证明其正确性。
所谓循环不变量是指一种在整个循环过程中保持不变的性质，它必须在以下3种情况下均保持不变，且该性质在循环终止后能证明算法的正确性。

  1. 初始化（循环的定义）

  2. 迭代（第 n 次迭代后，第 n+1 次迭代前）

  3. 结束（循环终止即循环条件判断为 false 时）

通俗点来说就是，只要你按照变量的定义严格保证变量在初始化，递归时，跳出循环时都保持不变的定义，那么就能证明你使用循环来推导问题是正确的。

同向指针解题步骤

这里还没有完全的整理所有的双指针，不敢妄自猜测会不会有不一般的情况。但这方法我觉得肯定是可以套用在所有的双指针问题上的，后续将继续更新双指针相关的题型。

解题步骤(重点来了)
1.定义指针 明确含义
2.确定终止条件
3.确定指针运动条件
4.根据定义确定返回值
重点:循环不变量的初始、迭代、退出时保持定义一致。

好了现在我们先拿26题看看怎么应用。

26. 删除排序数组中的重复

  1. 第一步 定义指针 明确指针的含义
    这里定义了两个指针,index 与 i,其中i是隐式的放在循环体里的。
    index:定义index表示不重复元素集合的右边界.用数学公式表示即[0,index)表示修改后的数组，因为左闭右开，所以index取不到
    有了变量定义，按照循环不变量的要求，我们先要确定初始化的时候是严格遵守定义的。初始化时不重复元素为空, 因为左闭右开，所以index = 0的时候,
    [0,0)是空集，满足要求。
  2. 确定循环终止条件
    如上面说的，这边还有个隐式的指针i(见代码),循环的终止条件就是i循环到数组的末尾。
    我这里总结的这类同向指针的题 其实都有这个特点，一个指针是循环指针，所以终止条件很简单。如果是对撞指针那么就会复杂些。类似于二分里面的left和right取不取等号
  3. 确定指针运动条件
    根据index的定义:不重复的元素的右边界，那么当有新的不重复的元素需要加入时index将向右移动。
    如何运动呢？这任然跟指针的定义有关系，用循环不变量的话来说:就是你得在循环的时候保持变量的定义不变。
    因为这里我们定义不重复元素集合是[0,index)左闭右开，因此index这个下标是可以用来放新的不重复元素的。同时index++;保持下一个循环时任然是[0,index）左闭右开。
  4. 根据定义确定返回值
    返回值是指新数组的长度，因为整个不重复元素集合是[0，index),即[0,index-1] 左闭右闭。因此一共有index-1 - 0 + 1个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int removeDuplicates(int[] nums) {
        // 1.定义[0,index)表示修改后的数组 即不重复的元素
        int index = 0; 
        // 2.终止条件
        for(int i = 0;i < nums.length;i++){
            // 3.指针运动条件
            if(index == 0 || nums[index-1] != nums[i]){
                nums[index] = nums[i];
                index++;
            }
        }
        // 4.根据定义确定返回值
        return index;
    }

至此上面这题就分析完了。这里我们还可以对index变量进行修改:[0,index] 表示不重复元素集合，分析过程写在下面的代码里，大家可以自行分析看看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 // 时间复杂度O(n) 空间复杂度O(1)
 public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length  == 0) return 0;
    // 1.指针定义 [0,index] 是修改后无重复的排序元素 注意 这里已经把0纳入进去了
    int index = 0; 
    // 2.另一个循环指针 从1开始，终止为nums.length，为什么从1开始 因为我们要比较重复 nums[0] 肯定是不重复的
    for(int i = 1;i < nums.length;i++){
        // 3.指针运动的条件
        if(nums[index] != nums[i]){
            index++;
            nums[index] = nums[i];
        }
    }
    // 4.根据定义确定返回值
    return index + 1;
}

因此不同的变量定义，会有不同的代码细节，如果靠死记硬背去学算法，就会被很多细节所搞蒙。

80 删除排序数组中的重复元素II

这里我觉得可以扩展一下,如果题目要求每个元素最多出现k次代码怎么写。
其实就是对于指针运动条件的考量，什么时候需要移动index指针?

  1. nums[i] != nums[index] 表示当前遍历的位置i和不重复集合的右边界不一样，那么肯定能放入不重复集合了。
  2. 题目要求每个元素最多出现k次,那么如果nums[i] != nums[index-k+1] 就可以保证不会存在连续的k个元素是值是重复的。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int removeDuplicates(int[] nums,int k) {
        if(nums == null) return 0;
        if(nums.length <= k) return nums.length;
        
        // 1.定义[0,index] 是修改后的满足要求的数组区间,这里已经把0 1 2 ...k- 1 ,共k个数 放进去了
        int index = k - 1;
        // 2.判断终止条件
        for(int i = k;i < nums.length;i++){
            // 3.指针移动条件
            if(nums[i] != nums[index-k+1]){
                index++;
                nums[index] = nums[i];
            }
        }
        // 4.判断返回值
        return index + 1;
    }

作者：liuchuan1992
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/solution/shuang-zhi-zhen-zhi-tong-xiang-zhi-zhen-che-di-jie/

点评：扣友！永远滴神！

-------------感谢阅读没事常来-------------