Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

原地算法的小总结

 
Category： DSA
  • zorchp
  • 2024年 03月07日

写在前面

好久没写博客了, 这次来总结一下原地算法(操作), 去年秋招被问到了两次, 感觉还是要好好理解一下的. (变式的题目比如手写 memcpy 本质上也是原地算法)

所谓原地算法, 就是在不用额外的空间(例如新开数组)的条件下, 仅遍历一次(或者有限次, 最后的时间复杂度仅为$O(N)$​)的一种算法, 其本质就是双指针(不过有时候不一定需要使用两根指针).

经典的排序算法中例如堆排序就用了原地操作来完成元素的上溯和下溯, 插入排序和选择排序中也是类似的原地操作.

在 C++的 STL 中有的算法就用到了这个思路, 比较常见的就是 vector 容器的 remove 操作, 用过的小伙伴应该知道 remove 不会真的删除所有的元素, 而是将待删除的元素移动到最后, 要想真的删除需要用 erase 才行, 具体可以参考 Effective STL 一书的 item9: 慎重选择删除元素的方法.

  #include <iostream>
  #include <vector>
  
  std::ostream &operator<<(std::ostream &os, std::vector<int> &v) {
     for (auto &x : v) {
         os << x << " ";
     }
     return os << std::endl;
  }
  
  void t1() {
     std::vector<int> v{1, 2, 1, 3, 1, 4, 1, 1, 2};
     std::cout << v;
     auto it = std::remove(v.begin(), v.end(), 1);
     std::cout << v;
     std::cout << std::distance(v.begin(), it) << std::endl;
     v.erase(it, v.end());
     std::cout << v;
     // 1 2 1 3 1 4 1 1 2
     // 2 3 4 2 1 4 1 1 2
     // 4
     // 2 3 4 2
  }
  
  int main(int argc, char *argv[]) {
     t1();
     return 0;
  }

可以看到 remove 一开始并没有把 1 全部删掉, 而是挪到了最后. 只有使用 erase 才能删掉.

原地算法基础

先来看两个基础的题目, 可以看成是两个模板

移动到末尾

一个直观的想法就是取一个新的数组, 然后把不为 0 的元素按顺序放在这个数组里面, 最后返回这个数组. 但是这样的空间复杂度就会比较大了, 而且也不符合原地修改的要求. 代码如下:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for (int i{}, j{}; i < n; ++i) {
            if (nums[i]) 
                ans[j++] = nums[i];
        }
        nums.swap(ans);
    }
};

想想可不可以一次遍历就能将所有的零都挪到最后呢?

来看下面的例子

0  1  0  3  0  12

现在我们关注的是数组中的 0, 但是仅移动 0 就可以了吗? 如果从后往前遍历, 每次把 0 挪到最后, 这时候其他元素的顺序不能保证了, 所以是不是可以换个思路呢?

试试移动非零的元素看看!

这次从前往后遍历, 但是不去管(目前不用管)数组中的 0, 而是看非零元素:

如果当前遍历到的是非零的元素, 那么就把这个值移动到数组的最前面, 而先不管数组中的 0, 这样操作下来, 得到的数组前半部分都是非零的元素了, 上面的例子来看就是

0  1  0  3  0  12  # 原始数组
1  1  0  3  0  12  # 遇到的第一个非零元素, 挪过去
1  3  0  3  0  12  # 遇到的第二个非零元素, 挪过去
1  3  12  3  0  12  # 遇到的第三个非零元素, 挪过去

这时候只需要记录最后一个非零元素被挪动到的位置索引, 然后遍历该位置到最后一个元素, 将这部分都设置成0 就可以了.

例子中就是

1  3  12  0  0  0  # 将索引位置往后的所有元素都设为 0

完成了!

来看代码: (需要两个循环)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), j{};
        for (int i{}; i < n; ++i) {
            if (nums[i]) {
                nums[j++] = nums[i];
            }
        }
        for (int i{j}; i < n; ++i) {
            nums[i] = 0;
        }
    }
};

照顾一下 Java 选手

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        for (int i = j; i < n; ++i) {
            nums[i] = 0;
        }
    }
}

当然了, 后来看了官方的题解, 发现可以写的更加简洁:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int n = nums.size(), i{}, j{}; i < n; ++i) {
            if (nums[i] != 0) {
                swap(nums[i], nums[j++]);
            }
        }
    }
};

不需要额外的补零了, 学习一下这种写法

移动到开头

看完了把某一类元素移动到最后的代码了, 都移动到最前面其实也比较简单了(反着遍历即可)

void move2head(vector<int> &nums) {
    // move 0 to the first of array
    int n = nums.size();
    int j{n - 1};
    for (int i{n - 1}; i >= 0; --i) {
        if (nums[i] != 0)
            nums[j--] = nums[i];
    }
    while (~j) nums[j--] = 0;// ~j means j != -1
}

这里大家可以写几个例子自行验证.

总结

看了上面的两个例子, 或者说模板, 相信你对于原地算法已经有了一个基本的认识了, 上面说了原地算法本质就是双指针, 那么这两根指针分别是什么呢?

其实就是第一次循环里面的变量 i 和 j, 其中 i 用来指向未遍历的元素, 而 j 在第一次遍历中用来指向不满足某些条件的元素(在上面的例子中就是非零的元素), 第二次遍历就比较 trivial 了, 用来恢复满足某些条件的元素(即上例中的零).

所以, 原地算法的本质就是 正难则反, 如果要移动 0 比较难, 那就移动非零元素, 最后直接把索引位置后面的元素都变成 0 即可.

有了上面的方法论, 下面的题也不是很难了.

原地操作其他题目

  1. 27. 移除元素 - 力扣（LeetCode）;

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

  2. 剑指 Offer 05. 替换空格 - 力扣（LeetCode）;(用到了27题的思想: 原地操作)

    class Solution {
public:
    string replaceSpace(string s) {
        if (s.empty()) 
            return s;
        int cnt{}, n = s.size();
        for (auto c : s) 
            cnt += (c == ' ');
        int nn = n + 2 * cnt;
        s.resize(nn);
        for (int r{n - 1}; r >= 0; --r) { // 反着遍历
            if (s[r] != ' ') {
                s[--nn] = s[r];
            } else {
                s[--nn] = '0';
                s[--nn] = '2';
                s[--nn] = '%';
            }
        }
        return s;
    }
};

  3. $\bigstar$151. 反转字符串中的单词 - 力扣（LeetCode）;(原地算法, 比较经典的一类应用)

    class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        int n = s.size(), idx{}; // idx 用于存放实际要挪到空字符位置的首索引
        for (int i{}; i < n; ++i) {
            if (s[i] == ' ') 
                continue;
            int r{i};
            if (idx) 
                s[idx++] = ' '; // 单词间的空格
            while (r < n && s[r] != ' ') 
                s[idx++] = s[r++]; // 空字符补位
            reverse(s.begin() + idx - (r - i), s.begin() + idx);
            i = r; // 直接更新起始位置
        }
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

  4. 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面;

    class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int n = nums.size(), l{};
        for (int r{}; r < n; ++r) {
            if (nums[r] & 1) 
                swap(nums[l++], nums[r]);
        }
        return nums;
    }
};

  5. 905. 按奇偶排序数组;

    class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int n = nums.size(), l{};
        for (int r{}; r < n; ++r) {
            if ((nums[r] & 1) == 0) 
                swap(nums[l++], nums[r]);
        }
        return nums;
    }
};
//
class Solution { //通解, 速度更快, 交换次数更少
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int l{}, r = nums.size() - 1;
        while (l < r) {
            while (l < r && (nums[l] & 1) == 0) ++l;
            // 遍历结束, l指向奇数
            while (l < r && (nums[r] & 1)) --r;
            // 遍历结束, r指向偶数
            if (l < r) swap(nums[l++], nums[r--]);
        }
        return nums;
    }
};

  6. 922. 按奇偶排序数组 II; 需要奇偶双指针, 找到不满足的才交换, 比较经典.

    class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        for (int n = nums.size(), i{}, j{1}; i < n; i += 2) {
            // i is always point to even number
            if (nums[i] & 1) { // odd 
                while (j < n and (nums[j] & 1)) 
                    j += 2; // find even number 
                swap(nums[i], nums[j]);
            }
        }
        return nums;
    }
};
search search_off backspace