Algorithm --> n位数去掉k位后找最小数

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

去掉K位求取最小数

一个n位的数，去掉其中的k位，怎样使留下来的（n-k）位数按原来的前后顺序组成的数最小

例如

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

解决方案

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

思路一

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

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

注意

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

参考代码

#include <iostream>
#include <cstdlib>
#include <cassert>
using namespace std;
int *q;int findMinIndex(int arr[], int beg, int end) //[]
{
if(beg > end)
return -;
int minv = arr[beg];
int minIndex = beg;
for(int i = beg + ; i <= end; ++i)
{
if(arr[i] < minv)
{
minv = arr[i];
minIndex = i;
}
}
return minIndex;
}int getRemain(int arr[], int size, int k)
{
assert(size > k && k >= );
int rev = , revIndex = -;
for(int i = size - k; i < size; ++i)
{
revIndex = findMinIndex(arr, revIndex + , i);
rev = rev * + arr[revIndex];
}
return rev;
}int main()
{
int arr[] = {, , , , , , };
size_t size = sizeof(arr) / sizeof(int); int remainNum;
for (int k = size-; k > ; --k)
{
int remainNum = getRemain(arr, size, size - k);
cout << "When k = " << k << ", the remaining value is:" << remainNum << endl;
}}

结果

分析

时间复杂度O(KN)

思路二

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

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

参考代码

#include <iostream>
#include <cassert>
using namespace std;int getRemain(int *arr, int size, int k)
{
assert(size > k && k > );
int tmp = size - k;
int cur = , pre;
int rev = ;
while(k != && cur < size)
{
pre = cur - ;
while(pre >= )
{
if(arr[pre] >= arr[cur])
{
for(int i = pre; i < size; ++i)
arr[i] = arr[i+];
--cur;
--k;
--size;
}
--pre;
}
++cur;
} for(int i = ; i < tmp; ++i)
{
rev = rev * + arr[i];
}
return rev;
}int main()
{
int arr[] = {, , , , , , };
size_t size = sizeof(arr) / sizeof(int); int remainNum;
remainNum = getRemain(arr, size, );
cout << "When k = " << << ", the remaining value is:" << remainNum << endl;
}

分析

时间复杂度O(KN)

Algorithm --> n位数去掉k位后找最小数的更多相关文章

[LeetCode] Remove K Digits 去掉K位数字
Given a non-negative integer num represented as a string, remove k digits from the number so that th ...
[LeetCode] 402&period; Remove K Digits 去掉K位数字
Given a non-negative integer num represented as a string, remove k digits from the number so that th ...
剑指offer43：左旋转字符串（字符串）：对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。
1 题目描述汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果.对于一个给定的字符序列S,请你把其循环左移K位后的序列输出.例如,字符序列S=”a ...
整数m去掉n位后剩下最大（小）值
题目描述给定一个正整数(<=255位),从中删去n位后,使得剩下的数字组成的新数最小(大): 思路:从左到右开始扫描,两两比较,如果是前一位比后一位大,则删去前大的一位,直到删完所有的n位: ...
编写函数digit(num, k)，函数功能是：求整数num从右边开始的第k位数字的值，如果num位数不足k位则返回0。
function digit(num,k){ var knum = 0; for(var i=1; i<=k; i++){ knu ...
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即&OpenCurlyDoubleQuote;XYZdefabc”。是不是很简单？OK，搞定它！
// test20.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include<iostream> #include&lt ...
取n的第k位
实例二:取n的第k位方法:a>> k & 1 某值a右移K位后与整数“1”进行与运算.即把需要第几位就右移几位. 例子: 0000 1000 ------8右移3位 0000 0 ...
一个n位的数，去掉其中的k位，问怎样去使得留下来的（n-k）位数按原来的前后顺序组成的数最小
例如 8314925去掉4个数,留下125最小,注意有前后顺序要求,要是没有顺序当然是123. 解决方案贪心算法,在每次被访问的位置保证有最优解. 思路一分析:求一共n位,求其中的m位组成的数最小 ...
Hulu面试题解答——N位数去除K个数字（解法错误sorry）
给定一个N位数,比如12345,从里面去掉k个数字.得到一个N-k位的数.比如去掉2,4,得到135,去掉1,5.得到234.设计算法.求出全部得到的N-k位数里面最小的那一个. 写的代码例如以下,思 ...

随机推荐

Node&period;js、Express框架获取客户端IP地址
Node.js //传入请求HttpRequest function getClientIp(req) { return req.headers['x-forwarded-for'] || req.c ...
用socket实现ping功能（记录）
/* 参考 http://bbs.csdn.net/topics/230001156 原文为win32版本稍有改动,以适应mac与linux系统 */ #include <stdio.h&gt ...
蜥蜴（bzoj 1066）
Description 在一个r行c列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外. 每行每列中相邻石柱的距离为1,蜥蜴的跳跃距离是d,即蜥蜴可以跳到平 ...
hdu 5542 The Battle of Chibi（2015CCPC - C题）
题目链接:hdu 5542 首届CCPC的C题,比赛时一起搞了好久,最后是队友A出的,当时有试过用树状数组来优化 dp,然后今天下午也用树状数组搞了一下午,结果还是踩了和当时一样的坑:我总是把用来记录 ...
git的初步使用
1.在GitHub上建立项目登录GitHub后,你可以在右边靠中那里找到一个按钮“New Repository”,点击过后,填入项目名称.说明和网址过后就可以创建了,然后会出现一个提示页面,记下类似g ...
docker网络访问（三）
docker网络访问 ifconfig查看网卡,启动docker的时候,docker会帮我们创建一个docker0的网桥. 1.随机映射 docker run -P 2.指定映射 -p hostPor ...
MySQL执行sql查询并上传至远程服务器
最近项目中有需要做一个shell脚本,可以对一个数据库执行sql操作,并将结果转为txt,筛选结果用tab隔开,保存至一个远程服务器上,以供其他人用Excel读取用txt中的内容. MySQL中将结果 ...
bzoj2006 NOI2010 数据结构+堆维护区间和最大
2006: [NOI2010]超级钢琴 Time Limit: 20 Sec Memory Limit: 552 MBSubmit: 3431 Solved: 1686[Submit][Statu ...
exporter API（导出、输出器api）moodel3&period;3
Moodle[导出器]是接收数据并将其序列化为一个简单的预定义结构的类.它们确保输出的数据格式统一,易于维护.它们也用于生成外部函数的签名(参数和返回值) 外部函数定义在moodle/lib/exte ...
[转]Spring通过&commat;Value注解注入属性的几种方式
原文地址:https://blog.csdn.net/csujiangyu/article/details/50945486 ------------------------------------- ...