C++模拟面试：从数组“紧凑”操作说开来

发表于 2年以前 | 总阅读数：379 次

假设用C语言来解答，字符串是char数组。O(n)时间复杂度实现不难，比如额外申请一个新数组，然后遍历一遍字符串，将符合条件的字符存储到新数组中，实现起来很简单。

但这显然不能让面试官满意。其实可以不开辟新数组空间实现。用两个变量i，j做游标，从前向后遍历。也算是算法题中“双指针”解法的一种题型了。


    char s[] = "1  2 3   4 5";
    int sz = strlen(s);
    int i = 0, j = 0;
    for (; j < sz; j++) {
        if (s[j] != ' ') {
            s[i] = s[j];
            i++;
        }
    }

题目二

一个整数数组，将0排到前面，非0在后，非0的相对顺序不变。

本题和上一题思路相同，只是两个游标从后向前。另外注意最后不要忘记给数组头部的元素设置0。

   int num[] = {1, 0, 0, 3, 0, 0, 0, 4, 5, 0, 2};
    int n = sizeof(num)/sizeof(int);
    int i = n - 1, j = n - 1;
    for (; j >= 0; j--) {
        if (num[j] != 0) {
            num[i] = num[j];
            i--;
        }
    }
    for (; i >= 0 ; i--) {
        num[i] = 0;
    }

这两个面试题其实也是工作中针对数组、链表的一种常见操作的简易表达。有时候我们从线性容器中删除元素，当时只是打上一个标记，并未真正删除，也未改变容器结构。在后面一个适当的时候，做一次处理，一次性批量地剔除本已删除的元素。彼时这个操作便是『compact』，或翻译成『紧凑』操作。

说开来

其实这个假删除，后来再compact的操作，在STL中早有体现，你了解吗？

C++ STL中的算法函数std::remove()便是如此，用remove来删除vector中元素时，它不会真的移除元素，它既不改变end()迭代器，也不改变成员函数size()、capacity()的值！

而且它不是将待删除元素交换到末尾，其只是做单向复制，比如vector 存储{0,1,0,3,12} 使用remove算法删除0后则是 {1,3,12,3,12}。最后两个元素3和12其实已然多余。

如果想要真的删除需要借助vector成员函数erase()。std::remove()执行完毕会返回一个迭代器，该迭代器指向首个被复制到尾部的元素的位置，也就是从这个位置到vector的end()，都是无效的元素，可被删除！


vector<int> v;
// 删除0
v.erase(remove(v.begin(), v.end(), 0), v.end());

std::remove()也可以操作list容器，效果同vector，也不是真实删除。但list其实提供了成员函数list::remove()，可以做删除操作，且是真实删除。另外list也有list::erase()成员函数.对于list而言，list::remove()和list::erase()的区别是：

remove()接收的参数是元素的值，而erase()接收的是迭代器，这点和vector相同。

关联容器（比如map）其删除函数的也名为erase()，接收迭代器参数，也是真实删除。

你会发现STL中erase()都是按迭代器来做删除（vector、list、map都有erase()成员函数），而remove()是按值删除（list成员函数或std::remove()）。

注意，如果在for循环中做顺序容器的删除操作，那么for循环的括号中，就不要做迭代器的累加操作了。这样很容易出问题，一般把迭代器的累加操作放到循环体中。