删数问题 | 删数

实践题目：删数问题

问题描述：

4-2 删数问题 (110 分)

给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。

输入格式:

第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式:

输出最小数。

输入样例:

在这里给出一组输入。例如：

178543
4

输出样例:

在这里给出相应的输出。例如：

算法描述：

这里这道题需要用到贪心算法，贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。（百度百科）

但是和常见简单的贪心算法不一样的是，为了让删数后的数最小，高位应该尽可能的小，所以在使用贪心算法策略的时候应该从最高位作比较删除。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main(){
    int n, i, j, k;
    string a;

    cin>>a>>n;
    int len=a.size();

    //删数过程（删掉k个数） 
    for(k=0; k<n; k++){
        for(i=0; i<len-1; i++){
            //从最高位开始比较，若a[i] > a[i+1]（高位比地位的数字更大），该位后面所有位往前挪一位（删掉a[i]）
            if(a[i] > a[i+1]){
                for(j=i; j<len-1; j++)
                    a[j] = a[j+1];
                break;
            }
        }
        //删掉一位后len--
        len--;
    }

    i = 0;
    //删数最后的数以0开头
    while(i <= len-1 && a[i] == '0')i++;

    //若全为0的情况
    if(i == len)
        cout<<"0"<<endl;
    //从第一个非0开始输出
    else
        for(j=i; j<=len-1; j++)
            cout<<a[j];

    return 0;
}

算法时间及空间复杂度分析：

删数过程中，k次循环删数中嵌套两个与输入字符串长度n相关的循环，则时间复杂度为：O(k*n*n)

删数完成之后，一次检查0的循环：O(n)

则最后的时间复杂度为：O(n²)

心得体会：

多刷题，多思考，多总结。