例如

8314925去掉4个数，留下125最小，注意有前后顺序要求，要是没有顺序当然是123。

解决方案

贪心算法，在每次被访问的位置保证有最优解。

思路一

分析：求一共n位，求其中的m位组成的数最小。那么这个m位的数，最高位应该在原数的最高位到第m位区间找，要不然就不能当第m位了，如下图（得到3位数最小，要是百位数在25中找，就当不了百位数了）：

同样找十位数时只能在百味数到目前位置中间搜，整个过程图示如下：

注意

在区间有多个最小值，取距离最大的，保证下一位数有足够大的查找空间。

参考代码

复制代码

include

include

include

using namespace std;
int *q;

int findMinIndex(int arr[], int beg, int end) //[]
{

if(beg > end)
    return -1;
int minv = arr[beg];
int minIndex = beg;
for(int i = beg + 1; i <= end; ++i)
{
    if(arr[i] < minv)
    {
        minv = arr[i];
        minIndex = i;
    }
}
return minIndex;

        

          
        
        
        

          

          AI 代码解读
        
      
      

}

int getRemain(int arr[], int size, int k)
{

assert(size > k && k >= 0);
int rev = 0, revIndex = -1;
for(int i = size - k; i < size; ++i)
{
    revIndex = findMinIndex(arr, revIndex + 1, i);
    rev = rev * 10 + arr[revIndex];
}
return rev;

        

          
        
        
        

          

          AI 代码解读
        
      
      

}

int main()
{

int arr[] = {3, 1, 6, 4, 8, 5, 7};
size_t size = sizeof(arr) / sizeof(int);

int remainNum;
for (int k = size-1; k > 0; --k)
{
    int remainNum = getRemain(arr, size, size - k);
    cout << "When k = " << k << ", the remaining value is:" << remainNum << endl;
}

        

          
        
        
        

          

          AI 代码解读
        
      
      

}
复制代码
结果

分析

时间复杂度O(KN)

思路二

分析：从前往后找，每次访问一位，比较该位前边的数，如果比该位大，果断干掉，例如：

同样以此往后遍历，知道干掉个数为k或访问到最后了，整个过程图示如下图。当然遍历到最后还没有干掉K个元素，说明剩下的已经为升序了，这样就在留下的数中取出前（n-k）个，整合成整数就是最小值。

参考代码

复制代码

include

include

using namespace std;

int getRemain(int *arr, int size, int k)
{

assert(size > k && k > 0);
int tmp = size - k;
int cur = 0, pre; 
int rev = 0;
while(k != 0 && cur < size)
{
    pre = cur - 1;
    while(pre >= 0)
    {
        if(arr[pre] >= arr[cur])
        {
            for(int i = pre; i < size; ++i)
                arr[i] = arr[i+1];
            --cur;
            --k;
            --size;
        }
        --pre;
    }
    ++cur;
}

for(int i = 0; i < tmp; ++i)
{
    rev = rev * 10 + arr[i];
}
return rev;

        

          
        
        
        

          

          AI 代码解读
        
      
      

}

int main()
{

int arr[] = {3, 1, 6, 4, 8, 5, 7};
size_t size = sizeof(arr) / sizeof(int);

int remainNum;
remainNum = getRemain(arr, size, 3);
cout << "When k = " << 3 << ", the remaining value is:" << remainNum << endl;

        

          
        
        
        

          

          AI 代码解读
        
      
      

}
复制代码
分析

时间复杂度O(KN)

本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3582857.html ，如需转载请自行联系原作者