陈利人 面试题 对于一个n位正整数a，去掉其中任意k(k<=n)个数字后，剩下的数字按原次序排列可以组成一个新的正整数。设计一个删数算法，使得剩下的数字组成的正整数最小。

题目

对于一个n位正整数a，去掉其中任意k(k<=n)个数字后，剩下的数字按原次序排列可以组成一个新的正整数。设计一个删数算法，使得剩下的数字组成的正整数最小。例如，a=13243221，k=5，输出：121。

分析

一个n位数，删去k位后，也就是剩下一个 n-k位 数，那么这个数要最小，我们就要保证我们我们得出的数是所有删除后得到的数的最小值。那么怎么保证呢？ 问题转换一下，如果最后就剩下一位，那么无意结果就是这些数字的最小值； 如果最后剩下两位呢，那么我们所要结果的最高位肯定在给定数的哪个区间呢，在这个区间（从左往右数第一位，从右往左数第二位），且是其中的最小值，而次最高位呢，肯定在哪个区间呢，在这个区间（刚才最高位+1，从右往左数第一位即是最后一位）；如果最后剩下三位数呢，有点长举个例子，数 20192，k=2，那么就是剩下三位数，最高位即百位肯定在这个区间（（从左往右数第一位，从右往左数第三位）），取最小数0即从左往右第二位，那么剩下的十位数字肯定在（刚才得到的那个最小值的位加一即从左往右数第三位，从右往左数第二位）这个区间里，取最小即是从左往右第三位1，接着最后结果的个位数字肯定在这个区间里（刚才得到的那个最小值的位加一即从左往右数第四位，从右往左数第一位）取最小值是2即是最后一位，程序结束的边境条件是搜索区间右界达到原数的从右往左数第一位，即最后结果三位数是012（所有的区间里位数都针对的是原数）；依次最后结果是五位，六位，七位。。。。。。。

时间复杂度

0（k*(n-k)） 一共有n-k数字，求每个数字要用的区间大小是k

实验室据

程序

#include<iostream>
using namespace std ;

const int K = 5 ;
const int size = 12 ;

void GetMinBit( int * data,int length,int start,int end,int &bit )
{
    if( data != NULL || length < 1 )
    {
        if( 0 <= start && start <= end && end < length )
        {
            int min = *(data+start) ;
            bit = start;       
            for( int i=start  ; i <= end  ;  i++ )
            {
                 if( *(data+i) < min )
                 {
                     min = *(data+i);                    
                     bit = i;
                 }       
            }   

        }
        else
        {
            cout<<"start "<<start<<" end "<<end<<" length "<<length<<endl ;
            system("pause") ;
        }
    }
    else
    {
        cout<<"length "<<length<<" data "<<data<<endl;
        system("pause") ;
    }
}

int GetMinData(int * data,int length,int k )
{
    if( data != NULL || length < 1 )
    {

        if( 0 <= k && k < length )
        {

            int result = 0 ;
            int bit = -1 ;
            int end = k ;
            while( end<length )
            {
                GetMinBit( data,length,bit+1,end,bit );
                result = result*10 + *(data+bit);                
                end++ ;
            }
            return result ;            
        }
        else 
        {
            cout<<"k "<<k<<" length "<<length<<endl;
            system("pause") ;
        }
    }
    else
    {
        cout<<"length "<<length<<" data "<<data<<endl;
        system("pause") ;
    }
} 



int main()
{
    int * data = new int[size];


    for(int i= 0 ;i<size ; i++ )
    {
         *(data+i)=rand()%10;
    }

    for(int i= 0 ;i<size ; i++ )
    {
         cout<<*(data+i)<<" ";
    }
    cout<<endl;

    cout<<"result "<<GetMinData( data,size,K )<<endl;
    system("pause");
    return 0;
}