#include <stdio.h>

/*感觉稍微难点的三个：

1）设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)

3）设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，则中国人民 人民中国都有效。要求：

  1）系统每秒的查询数量可能上千次；

  2）词语的数量级为10W；

  3）每个词至多可以与1W个词搭配

 

 当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息.

 */

/*2）一串首尾相连的珠子（m个），有N种颜色（N《=10），设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。

time: O(m)

space: O(N)*/

#define MAX_N 10

bool Select(int m, int const *data, int n, int *start_idx, int *length)

{

    int color[MAX_N];

    int nColor=0;

    memset(color, 0, sizeof(color));

    *start_idx = 0, *length = m;

    

    int best_start_idx = 0;

    int best_length = m;

    for(int i=0; i<m-n; i++)

    {

        if(!color[data[i]]) nColor++;

        color[data[i]]++;

        if(nColor==n && i-best_start_idx+1<best_length)

        {

            best_length = i-best_start_idx+1;

            *start_idx = best_start_idx;

            color[data[best_start_idx]]--;

            if(0==color[data[i]])

                nColor--;

            else

                i--;

            best_start_idx++;

        }

    }

    return true;

}

int main(int argc, char *argv[])

{

    int n=6;

    int data[]={0,1,2,3,4,4,5,4,2,3,1,0,2,3};

    int m = sizeof(data)/sizeof(data[0]);

    int start_idx;

    int length;

    Select(m, data, n, &start_idx, &length);

    return 0;

}