玩转算法面试之数组（一）

作者: 爱笑的云里看梦 | 来源:发表于2018-03-26 21:08 被阅读262次

算法面试之数组

从实战的经典算法题出发，以LeetCode上的题目为例，一点点剖析与优化。
LeetCode 283:Move Zeros
给定数组nums，将其中为0的元素挪到末尾，其它元素位置保持不变
这道题目非常简单，我们马上就会想到可以遍历一遍数组。对非零元素做处理，就像下面这样。

最简单的算法也可以优化
- 遍历一边数组，将所有的非零元素拿出来赋给新的数组，其余元素都置0.
  此中方法最为直观，也是最容易想得到。算法代码如下：
```
void moveZeros(vector<int> &nums) {
    //定义一个新的数组用于存放非零元素。
    vector<int> nonZeroElements;
    //遍历一遍原来的数组，将非零元素放进nonZeroElements
    for(int i = 0; i < nums.size(); ++i) {
        if(nums[i])
           nonZeroElements.push_back(nums[i]);
    }
    //再将nonZeroElements的元素放进原来的数组nums里。因为要求在nums中改变
    for(int i = 0; i < nonZeroElements.size; ++i) {
        nums[i] = nonZeroElements[i];
    }
    //剩下的元素都置0
    for(int i = nonZeroElements.size(); i < nums.size(); ++i) {
        nums[i] = 0;
    }
}
```
这种算法可以AC过，但是显示不是合适和优秀的解法。因为这个算法的时间复杂度为O(N)，因为我们申请了另外一个vector，所以空间复杂度也为O(N)。
怎么样优化算法，使之成为一个原地算法，即不需要其他的辅助空间？
- 另一种算法
  对于数组nums，我们可以设置两个指针i和k，分别指向要遍历的元素和遍历过的非零元素。在i指针进行遍历的时候：
  1.如果nums[i]的值不为0，那就将它和指针k+1位置的元素进行交换。
  2.如果nums[i]为0，那么就跳过，即i++，k不变。
  这样，当i遍历到最后一个的时候，所有非零元素就都被移动到最末尾去了。
  因为首次遍历的时候非零元素还一个都没有，所以k最先指向-1.
  算法代码如下：
```
void moveZeros(vector<int> &nums) {
    for(int i = 0,k = -1; i < nums.size(); ++i) {
        if(nums[i])
           swap(nums[i],nums[++k]);
    }
}
```
怎么样，这样的代码是不是看上去比之前写的那个好多了。而且它并没有用到额外的辅助空间，比上一个算法优化了一点。
其实，上面这个算法做了一些重复的操作，想一下，当数组中的元素全是非零元素会怎么样呢？答案是每次循环都会做一次swap操作！所以，还可以进行如下优化：
```
void moveZeros(vector<int> &nums) {
    for(int i = 0,k = 0; i < nums.size(); ++i) {
        if(nums[i])
           if(i != k)
               swap(nums[i],nums[k++]);
           else
               k++;
    }
}
```
这样，对于数组中都是非零元素，swap函数就不会执行。
对于一些基础算法，我们怎么去应用它呢？下面，我们看一道LeetCode的入门题目:
LeetCode 75: Sort Colors
给定一个有n个元素的数组，数组中元素的取值只有0， 1， 2这三种可能，为这个数组排序.
对于这个问题，首先想到的是各种排序算法，尤其是时间复杂度为O(nlgn)的排序算法，例如快排。当然这是一个最常规的方法。也是基础应该知道的方法。但是，这并没有用到题目给出的条件：“数组中元素的取值只有0， 1， 2这三种可能”。那么，对于这个问题，有比O(nlgn)更快的方法吗？
想一下：因为原数组中只有0，1，2三种数字，那么我们可以通过遍历一次数组，分别统计下0，1，2的个数，然后再将他们放回到原数组中去就好了。这种思想就是计数排序的思想。
算法代码如下：

void sortColors(vector<int> nums) {
    //数组count的值对应的是0，1，2出现的次数
    int count[3] = {0};
    for(int i = 0; i < nums.size(); ++i) {
       assert(nums[i] >= 0 && nums[i] <= 2);
       count[nums[i]] ++;
    }
    int index = 0;
    for(int i = 0; i < count[0]; i++)
       nums[index ++] = 0;
    for(int i = 0; i < count[1]; i++)
       nums[index ++] = 1;
    for(int i = 0; i < count[2]; i++)
      nums[index ++] = 2;
}

这个算法虽然可以工作，但是看起来似乎还是不能令人满意。因为如果数字多了就不好处理了。
下面考虑一下优化的方法：将数组中选定v作为标定数，在v之前的都小于v，之后的大于v。这样分别再对v之前和之后的选取标定数进行递归排序。这种思想就是三路归并的思想。由于在本题中只有0,1,2三种元素，所以可以分为大于1和小于1两种。
思想描述
* 设置三个索引指针:zero,two和i。其中 zero表示zero指针之前的元素都为0（包括zero本身）,two表示two指针之后的元素都为2（包括two本身）。i代表遍历的每一个元素。要注意，对于i来说，它只需要小于two就可以了。
* 对于i指向的元素
- 如果nums[i] == 1,那么只需要将i指针加一即可
- 如果nums[i] == 0,那么需要把它与zero指针+1位置的元素进行交换即可。然后i++,因为zero+1处的元素必定为1.
- 如果nums[i] == 2，那么将它与two-1位置的元素进行交换，注意，i值不发生变化，因为此时并不知道，交换过来的值是什么。
* 当i的值指向two处，遍历结束，数组便重新有序了。
算法代码如下：

void sortColors(vector<int> nums) {
    int zero = -1;
    int two = nums.size();
    for(int i = 0; i < two;/*i的值不在这里改变*/ ) {
        if(nums[i] == 1) {
            i ++;
        } else if(nums[i] == 0) {
            swap(nums[++zero],nums[i++]);
        } else if(nums[i] == 2) {
            swap(nums[--two],nums[i]);
        }
    }
}

这样，我们通过设置两个哨兵就解决了这个问题。而且只需要遍历一次数组就可解决这个问题。时间复杂度是O(N)的。

下面是LeetCode上与这两个题相关的一些经典数组题目。大家可以当做LeetCode刷题入门来做。在得到AC之后，希望你还能有更好的解决办法把算法进行优化。这在面试过程中是一个很棒的加分项。当然，最重要的是解决问题，即使面试中没法快速想到最优方法，那就用最常规的方法去解决。因为对于一个问题来说，肯定是先把它解决掉，然后再进行优化。

注意:在下一篇文章中将会给出下面题目的解决思路与源代码。

LeetCode 27:Remove Element