赵成的算法博客

下面这个题是我在电话面试里被问到的，确实有一个很简单的解法，但是我觉得现场尤其是电话面试里给出线性时间解法基本就是不可能的，除非以前遇到过相似的问题。所以很难说这种题目考察出来的究竟是你编码的能力，还是说考察你有没有碰巧做过类似的题目。好了，吐槽完毕。

传说百度笔试题目：

有一串首尾相连的珠子，共有m个，每一个珠子有一种颜色，并且颜色的总数不超过n(n<=10)，求连续的珠子的颜色总数为n时，长度最小的区间。可简述思路或者给出伪代码，并且给出时间和空间复杂度分析。

这个题目实际上和“字符串内寻找包含所有字符的最小子字符串”的问题是一样的，而且更简单，我的解法的思路来自这里。

最不靠谱的解法就是通过下标来循环遍历，这类问题最好以窗口的方式思考，通过移动窗口的左右边来寻找最佳的答案。

假设窗口的左右边为begin和end，初始时都指向第一个元素，接着移动end，直到找到第一个符合要求的窗口（即包含所有颜色），然后移动begin，在保证窗口符合要求的情况下尽可能地减小窗口大小，减小到最少时我们就得到了一个可能的解。然后再移动end和begin，循环往复，直到end走到尽头。

这样最坏情况下begin和end都会移动n次，也就是时间复杂度O(n)。

实现细节：

移动begin时如何保证满足窗口要求？

要求实际上就是每种颜色至少出现一次，移动end时可以记录下每种颜色出现的次数，接着begin所在的颜色只要数目大于1，就可以继续移动（要记得移动后减小颜色数目）

这个题目之前也有他人做过，在这里，答案有些太复杂了。

如果考虑到环的情况，可以用下面两种方法补充：

1. 数组原样在后面接上一份，如ABC变为ABCABC
2. 遍历时改为遍历到2n -1，写下标时取模，如end变为end%n

代码如下：

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minimum_interval(int *a, int n, int m, int *ob, int *oe)
{
    int found[m];
    bzero(found, m * sizeof(int));

    int count = 0;
    int min = INT_MAX;
    int begin, end;
    for (begin = end = 0; end < n; ++end) {
        if (!found[a[end]])
            ++count;
        ++found[a[end]];

        if (count == m) {
            while (found[a[begin]] > 1) {
                --found[a[begin]];
                ++begin;
            }

            if (end - begin < min) {
                *ob = begin;
                *oe = end;
                min = end - begin;
            }
        }
    }

    return count == m;
}

int main(int argc, char *argv[])
{
    int a[] = { 0, 1, 1, 0, 0, 0, 2, 3, 3, 4, 5, 6, 1 };
    int begin, end;
    minimum_interval(a, 13, 7, &begin, &end);
    printf("begin: %d, end: %d\n", begin, end);
    for (int i = begin; i <= end; i++) {
        printf("%d ", a[i]);
    }
    
    return 0;
}

关于划分，大家在讨论快排时已经说得比较多了，这里我主要说说如何在空间复杂度为O(1)的情况下进行稳定的划分。

首先看两道面试题：

百度面试题（一）：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。

百度面试题（二），给定一个存放正数的数组，重新排列数组使得数组左边为奇数，右边为偶数，且保证奇数和偶数之间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。

这两道题是搜面试题时从这里找到的，说老实话，里面的答案真是不够靠谱的……

这两题的本质就是划分，划分条件分别是为负数和为奇数，另外附加有稳定和无额外空间需求的条件，C++里直接用std::stable_partition做就好。

不过有一个小小的陷阱，C++标准里并没有规定std::stable_partition的空间复杂度，而且std::stable_partition实际上需要的空间确实为O(n)。下面说一下如何实现无需额外空间的inplace stable partition。

我采用分而治之的方式来进行处理，把数据劈成两半，两边分别进行递归处理，这时我们可以确定两边都已经划分完毕，以第二题为例，那么我们得到了|正数1|负数2|正数3|负数4|的排列，只需要把中间的两端交换一下就可以了，变为|正数1|正数3|负数2|负数4|。

细节问题：

1. 相邻区间交换可以用std::rotate，时间复杂度为O(n)
2. partition函数需返回划分处，要注意rotate之后划分处的计算
3. 对于只有一个数的情况想想什么才是正确的返回值

下面是第二题的范例代码，出于演示的目的就没有做成通用型的了。

#include <stdio.h>
#include <algorithm>
using std::rotate;

bool predicate(int i)
{
    return i > 0;
}

int inplace_stable_partition(int *a, int i, int n)
{
    if (i == n - 1)
        return predicate(a[i]) ? i + 1 : i;

    int middle = i + (n - i) / 2;
    i = inplace_stable_partition(a, i, middle);
    n = inplace_stable_partition(a, middle, n);

    rotate(a + i, a + middle, a + n);
    return i + n - middle;
}

int main(int argc, char *argv[])
{
    int a[] = { 1, -1, 2, -2, 3, -3 };
    inplace_stable_partition(a, 0, 6);
    for (int i = 0; i < 6; i++)
        printf("%d ", a[i]);
    
    return 0;
}