LeetCode数组的解题技巧

上文介绍了数组的基本操作以及其时间复杂度。

本文结合LeetCode题目，介绍数组的解题技巧。

多下标

使用一个下标遍历数组。

也可以使用2个或者多个下标，每个下标代表不同的含义。

区间

2个下标可以组成区间，区间可以代表明确的含义：比如相同的元素区间。

元素交换

在数组中交换两个不同下标的值，其时间复杂度是O(1)。

可以代替数组的删除或者插入操作，它们的时间复杂度是O(n)。

LeetCode 283

 来源：力扣（LeetCode）283 Easy
 链接：https://leetcode-cn.com/problems/move-zeroes
 
 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

 示例:
 输入: [0,1,0,3,12]
 输出: [1,3,12,0,0]
 
 说明:
 必须在原数组上操作，不能拷贝额外的数组。
 尽量减少操作次数。

解题思路

• 定义下标i，区间[0,i)的含义：非0元素区间
  • 不断地寻找非0元素，将非0元素交换到该区间，并扩大区间
  • 区间包括0，不包括i
• 定义下标j，用于遍历数组，找到非0元素
  • 交换i和j的值
  • 扩大非0元素区间

C++

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // [0,i)的元素均为非0元素
        int i = 0; 
        vector<int>::size_type length = nums.size();
        for(int j = 0 ; j < length ; j++) {
            // 找到非0元素，交换到区间[0,i)
            if(nums[j] != 0) {  
                if (i != j) {       
                    swap(nums[i], nums[j]);
                    i++;
                } else {
                    // 数组内都是非0元素的情况
                    i++;
                }
            }
        }
    }
};

Swift

class Solution {
    func moveZeroes(_ nums: inout [Int]) -> Void {
        // [0,i)的元素均为非0元素
        var i = 0
        
        let length = nums.count
        for j in 0..<length {
            // 找到非0元素，交换到区间[0,i)
            if nums[j] != 0 {
                if i != j {
                    nums.swapAt(i, j)
                    i += 1
                } else {
                    // 处理所有元素都是非0的情况
                    i += 1
                }
            }
        }
    }
}

LeetCode 27

 来源：力扣（LeetCode）27 Easy
 链接：https://leetcode-cn.com/problems/remove-element
 
 
 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 示例 1：
 输入：nums = [3,2,2,3], val = 3
 输出：2, nums = [2,2]
 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
 
 示例 2：
 输入：nums = [0,1,2,2,3,0,4,2], val = 2
 输出：5, nums = [0,1,4,0,3]
 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

解题思路

上题是本题的特例：

• LeetCode 283是移除0元素，保留其他元素
• 本题LeetCode 23是移除指定元素，保留其他元素

解题思路

• 定义下标i，区间[0,i)的含义：非指定元素区间
  • 不断地寻找非指定元素，将指定元素交换到该区间，并扩大该区间
• 定义下标j，用于遍历数组，找到非指定元素
  • 交换i和j的值
  • 扩大非指定元素区间

C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // [0,i)的元素均为非指定元素
      	// i也表示区间长度
      	int i = 0; 
        vector<int>::size_type length = nums.size();
        for(int j = 0 ; j < length ; j++) {
            // 找到非指定元素，交换到区间[0,i)
            if(nums[j] != val) {      
                if (i != j) {       
                    swap(nums[i], nums[j]);
                    i++;
                } else {
                    // 数组内都是非指定元素的情况
                    i++;
                }
            }
        }
        
        return i;     
    }
};

Swift

class Solution {
    func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
        // [0,i)的元素均为非指定元素
        // i也表示区间长度
        var i = 0
        
        let length = nums.count
        for j in 0..<length {
            // 找到非0元素，交换到区间[0,i)
            if nums[j] != val {
                if i != j {
                    nums.swapAt(i, j)
                    i += 1
                } else {
                    // 数组内都是非指定元素的情况
                    i += 1
                }
            }
        }
        
        return i
    }
}

LeetCode 80

 来源：力扣（LeetCode）80 Medium
 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii
 
 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 
 示例 1：

 输入：nums = [1,1,1,2,2,3]
 输出：5, nums = [1,1,2,2,3]
 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
 
 示例 2：

 输入：nums = [0,0,1,1,1,1,2,3,3]
 输出：7, nums = [0,0,1,1,2,3,3]
 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

解题思路

数组有序，表示左边保留的元素，右边是不会再次出现。

• 定义下标i和j，区间[i,j)的含义：最新的保留元素区间
  • 区间内是相同元素，其长度不大于2
  • 最新的含义：找到不同元素之后，需要向右移动该区间，再将该元素移动到新区间
  • j也表示新数组的长度
• 定义下标k，用于遍历数组
  • 如果k元素等于当前区间元素，尝试扩大区间
  • 否则，向右平移区间，将k元素交换到该区间

C++代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // [i,j)表示最新的保留元素区间
        // j也表示新数组长度
        int i = 0;
        int j = 0;
        
        vector<int>::size_type length = nums.size();
        for(int k = 0 ; k < length ; k++) {
            int i_num = nums[i];
            int k_num = nums[k];
            if (i_num == k_num) {
                // 当前区间小于2，把k_num交换到[i,j)
                // 再扩大区间
                if (j - i < 2) {
                    if (j != k) {
                        swap(nums[j], nums[k]);
                    }
                    j++;
                }
            } else {
                // 向右移动区间，将新的元素nums[k]交换到该区间
                i = j;
                j = j + 1;
                if (i != k) {
                    swap(nums[i], nums[k]);
                }
            }
        }

        return j;
    }
};

Swift

class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        // [i,j)表示最新的保留元素区间
        // j也表示新数组长度
        var i = 0;
        var j = 0;
        
        let length = nums.count;
        for k in 0..<length {
            let iNum = nums[i];
            let kNum = nums[k];
            if (iNum == kNum) {
                // 当前区间小于2，把kNum交换到[i,j)
                // 再扩大区间
                if (j - i < 2) {
                    if (j != k) {
                        nums.swapAt(j, k)
                    }
                    j += 1;
                }
            } else {
                // 向右移动区间，将新的元素nums[k]交换到该区间
                i = j;
                j = j + 1;
                if (i != k) {
                    nums.swapAt(i, k)
                }
            }
        }

        return j
    }
}

GitHub地址：
https://github.com/Anzeron/Structure-Algorithm-LeetCode

阅读原文，关注公众号[空与一]