(1) 问题描述: 给定 n 位正整数 a, 去掉其中任意 k <= n 个数字后, 剩下的数字按原来次序排列组成一个正整数. 对于给定的 n 为正整数 a 和正整数 k 设计一个算法找出剩下数字组成的新数最小的删数方案;
(2) 算法设计: 对于给定的正整数 a, 计算删去 k 个数字后得到的最小数;
(3) 算法思想: 删掉要删的, 留下要留的; 在给定的数 a, 对于其每一位上的数, 采用贪心算法, 局部最优的方式, 留下最小的数位; 前提: 在删除过程中, 急要保证该位上的数字最小, 又要确保删除数时够删的原则;
(4) 核心代码:
- public class DeleteData {
- /**
- * 给定的正整数
- */
- private static Integer num;
- /**
- * 存放数据数组
- */
- private static Integer[] data;
- /**
- * 删除总数
- */
- private static Integer total;
- /**
- * 删除标识
- */
- private static Boolean[] deleteFlag;
- /**
- * 初始化数据
- */
- private static void initData() {
- Integer index = 0;
- Scanner input = new Scanner(System.in);
- System.out.println("请输入给定的正整数:");
- String numStr = input.nextLine();
- num = Integer.valueOf(numStr);
- System.out.println("请输入删除正整数的个数:");
- total = input.nextInt();
- data = new Integer[numStr.length()];
- deleteFlag = new Boolean[numStr.length()];
- // 拆分 num 元素, 存放到 data 数组 [178543 --> data = {3, 4, 5, 8, 7, 1}]
- while(num != 0) {
- data[index] = num % 10;
- num = num / 10;
- deleteFlag[index] = false;
- index++;
- }
- // data 数组逆置
- for (int i = 0, j = data.length - 1; i <j; i++, j--) {
- Integer temp = data[i];
- data[i] = data[j];
- data[j] = temp;
- }
- }
- /**
- * 删除
- */
- private static void deleteData() {
- int find = 0; // 初始从下标为 0 开始找
- while(total != 0) {
- int min = 10;
- int index = -1;
- // data.length - i 表示在下标为 i 后面剩余的数字, 大于等于要查找的数字个数 total, 确保够删
- for (int i = find; i < data.length && data.length - i>= total; i++) {
- if (data[i] <min) {
- min = data[i];
- index = i;
- }
- }
- if (index>= 0) {
- deleteFlag[index] = true; // 留下要留的数字
- }
- find = index + 1; // 下次寻找直接从 index 的下一位开始, 因为当前位已经是最小的, 不必重复查找
- total--;
- }
- }
- /**
- * 输出
- */
- private static void print() {
- System.out.println("删除后最小值为:");
- for (int i = 0; i < deleteFlag.length; i++) {
- if (deleteFlag[i]) {
- System.out.print(data[i]);
- }
- }
- }
- public static void main(String[] args) {
- // 初始化数据
- initData();
- // 删除
- deleteData();
- // 输出
- print();
- }
- }
(5) 输入输出:
请输入给定的正整数:
178543
请输入删除正整数的个数:
2
删除后最小值为:
13
(6) 总结: 删数问题极大的反应出贪心算法的思想, 每次循环删数时, 都寻找局部最优解, 最后删除完之后, 留下的就是最优解;
来源: http://www.bubuko.com/infodetail-3415874.html