一个n位的数,去掉其中的k位,问怎样去使得留下来的(n-k)位数按原来的前后顺序组成的数最小

简介:

例如

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;

}

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;

}

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;
}

}
复制代码
结果

分析

时间复杂度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;

}

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;

}
复制代码
分析

时间复杂度O(KN)

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

相关文章
|
2月前
|
人工智能 分布式计算 运维
感叹opds的强大
感叹opds的强大
|
7月前
|
前端开发 程序员 API
鸿蒙元服务实战-笑笑五子棋(1)
《笑笑五子棋》是基于鸿蒙系统开发的元服务应用,由深度开发者分享开源。名字源于开发者女儿“笑笑”,充满程序员的独特浪漫。应用采用 ArkTS API 12、Canvas 等技术,支持 AtomicServiceTabs 和卡片开发,已成功上架并获得基础激励。凭借活跃设备数达标,还登上鸿蒙负一屏休闲分类菜单,提升了用户活跃度。本文介绍了应用背景和技术细节,下篇将聚焦代码实现。适合对鸿蒙开发感兴趣的开发者学习交流。
136 10
鸿蒙元服务实战-笑笑五子棋(1)
|
人工智能 安全 搜索推荐
未来智能家居系统的发展趋势
随着人工智能和物联网技术的飞速发展,智能家居系统正日益融入人们的生活。本文将探讨未来智能家居系统的发展趋势,分析其在家庭生活、能源管理、安全保障等方面的创新应用,展望智能家居系统为我们带来的便利与改变。
【C++】类与对象(三) 运算符重载 赋值重载 取地址及const取地址操作符重载(1)
【C++】类与对象(三) 运算符重载 赋值重载 取地址及const取地址操作符重载
|
存储 前端开发 NoSQL
SpringSecurity在微服务中应用实践思考
SpringSecurity在微服务中应用实践思考
243 0
|
存储 算法 数据可视化
浮点数美丽的表象(为什么要慎用浮点数)
这其实是float累加过程中精度丢失导致的,要理解这点我们首先要理解什么是浮点数。首先我们了解数在计算机中是如何表示的,因为计算机只能理解0和1两个数,所以一切信息都是用二进制表示的。如何保存更多的信息就是计算机设计者面临的挑战。
112 0
|
弹性计算 IDE 开发工具
阿里云插件新版发布,多特性助力提升开发者体验
Cloud Toolkit 2018.12 新版本发布,提供了在 Intellij IDEA 内置Terminal 功能,能够允许开发者通过 Cloud Toolkit 登陆远程服务器终端 Terminal。
2582 92
|
存储 JavaScript
【ES6】Set 对象
【ES6】Set 对象
211 0
|
机器学习/深度学习 人工智能 边缘计算
Gartner发布2021年一定要关注的十大数据和分析技术趋势
Gartner发布2021年一定要关注的十大数据和分析技术趋势
133 0
|
运维 监控
平方预测误差(Squared prediction error,SPE)和霍特林统计量(Hotelling’s T2)原理
平方预测误差(Squared prediction error,SPE)和霍特林统计量(Hotelling’s T2)原理
平方预测误差(Squared prediction error,SPE)和霍特林统计量(Hotelling’s T2)原理