一、实践题目
删数问题二、问题描述
给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。
三、算法描述
1.采用贪心法。贪心策略是:删除从左到右第一个递减序列的第一个数,当序列是非递减时,删除最后一个数。
2.循环第一步k次。
3.利用flag删除前置的0。
四、算法时间复杂度以及空间复杂度的分析
时间复杂度:O(nk)
空间复杂度:O(1)
五、心得体会
一开始我们采用的是找出序列中最大的数进行删除,但是发现这样是不对的,对此我认为选择一个正确的贪心策略是非常重要的。
六、贪心算法的个人体会和思考
1、贪心算法的贪心选择性质和最优子结构性质是很重要的。
2、在某些情况下,贪心算法并不能得到最优结果。