微软面试100题(92):捣乱分子

1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的), 那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:
176, 178, 180, 170, 171
这些捣乱分子对为
<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)
要求：
输入:
为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。
输出：
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。
详细说明自己的解题思路，说明自己实现的一些关键点。
并给出实现的代码，并分析时间复杂度。
限制：
输入每行的最大数字个数为100000 个，数字最长为6 位。程序无内存使用限制。

 

该题一看明显ACM搬过来的。直观感受DP，但是还想了挺久。给出的DP算法是核心算法，存储结构如果用线段树来处理数据结构可以优化不少。但是就题干给出的数据，直接使用二维数组就足够而且简单了。

 

设f(i,v)为从下标为i的元素开始，其后面值不小于input[i]的值的个数,即从i开始向后，非捣乱分子的个数。

那么有,

           f(i-1,v) = f(i,v) + 1(input[i]<=v)

                      f(i,v)    (input[i]>v)

捣乱分子个数g(i,v) = size - i -f(i-1,v)

求和即可。

 

该算法复杂度为O(n*m),m为输入数据的最小值与最大值的差值。

 

该算法空间复杂度较高（DP的空间换时间特性），而且时间复杂度和输入数据的分布有关。如果说所有数据都不相等，且差值较大，该算法就会严重退化。（此处如果使用线段树存储数据，可以大大减少空间时间复杂度，不过数据结构的处理就会变得挺麻烦了）。

如果如题目中给出的类似于身高的数据范围很小，给出的算法就非常合适了。

网络上给出的多为类于归并排序的算法，不赘述。

 

 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
int result[MAX][MAX] = {{0}};
void fillResult(int * input, int size, int min, int max){
    int i = size -1;
    for(;i>= 0 ; i--){
        int v = min;
        for(;v<=max;v++){
            result[v][i] = v<=input[i]?(result[v][i+1] + 1) : result[v][i+1];
            printf("%d, %d = %d \n", v,i,result[v][i]);
        }
    }
}
int mygetCount(int * input, int size){
    int count = 0;
    int i = 0;
    for(;i<size;i++){
        count += (size-i- result[input[i]][i]);
        printf("count = %d \n", count);
    }
        return count;
}

int main(){
    int input[] = {1,3,2,5,4};
    fillResult(input, sizeof(input)/sizeof(int), 1, 5);
    printf("%d \n", mygetCount(input, sizeof(input)/sizeof(int)));
}