【AcWing每日一题】4653. 数位排序

简介: 【AcWing每日一题】4653. 数位排序

小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。


当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。


例如,2022 排在 409 前面,因为 2022 的数位之和是 6,小于 409 的数位之和 13。


又如,6 排在 2022 前面,因为它们的数位之和相同,而 6 小于 2022。


给定正整数 n,m,请问对 1 到 n 采用这种方法排序时,排在第 m 个的元素是多少?

输入格式

输入第一行包含一个正整数 n。

第二行包含一个正整数 m。

输出格式

输出一行包含一个整数,表示答案。
数据范围

对于 30% 的评测用例,1≤m≤n≤300。

对于 50% 的评测用例,1≤m≤n≤1000。

对于所有评测用例,1≤m≤n≤106

输入样例:

13
5

输出样例:

3

样例解释

1 到 13 的排序为:1,10,2,11,3,12,4,13,5,6,7,8,9。

第 5 个数为 3。


我的思路:

  • 对于50%的样例,是可以用暴力枚举的
  • 首先,开一个长度为106的数组,用来存储排序后的每一个数
  • 这里采用输入的同时排序,时间复杂度是够用的
    排序使用可以降低复杂度的二分算法
  • 排好之后直接输入m位置上的数即可

对于50%样例的代码:

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
int position(int i, int len){
  if(len == 0) return 1;
  int sum = 0, cnt = i;
  while(cnt){
    sum += cnt%10;
    cnt /= 10;
  }
  int low = 1, high = len, mid;
  while(low <= high){
    mid = (low+high)/2;
    int sum_mid = 0, cnt_mid = a[mid];
    while(cnt_mid){
      sum_mid += cnt_mid%10;
      cnt_mid /= 10;
    }
    if(sum > sum_mid || (sum == sum_mid && i > a[mid])) 
      low = mid+1;
    else if(sum < sum_mid || (sum == sum_mid && i < a[mid])) 
      high = mid-1;   
  }
  return low;
}
int main(){
  int n, m, k = 0;
  cin >> n >> m;
  for(int i = 1; i <= n; i++, k++){
    int index = position(i, i-1);
    for(int j = i-1; j >= index; j--){
      a[j+1] = a[j];
    }
    a[index] = i;
  }
  cout << a[m];
  return 0;
}

查找位置的复杂度为O(nlog2n),所有总的复杂度为O(n2log2n),对于所有的样例肯定会TLE

优化思路:

  • 对于上面的106长度的数组,进行改进
  • 由于所有数所能产生的数位和的数量是有限的,所以可以考虑用散列表的形式进行存储
    对于每一个数,用所得到的数位和作为散列地址
  • 利用拉链法,使得相同数位和的数(同义词)存储在同一散列地址的链表下
  • 对于同一个数位和的不同数,后面来的一定比前面来的要大,所以可以不用链表,直接用数组

代码:(可以AC)

#include<iostream>
#include<vector>
#include<map>
using namespace std;
map<int, vector<int> > dic;
int main(){
  int n, m, k = 0, len = 0;
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    int cnt = i, sum = 0;
    while(cnt){
      sum += cnt%10;
      cnt /= 10;
    }
    if(dic.find(sum) == dic.end()){
      dic[sum] = vector<int>(0);
    }
    dic[sum].push_back(i);
  } 
  //对于map的遍历有点忘了
  //下面这段代码来源:https://www.acwing.com/solution/content/159370/ 
  for (const auto &i: dic){
        if (m > i.second.size())    m -= i.second.size();
        else{
            cout << i.second.at(m - 1);
            break;
        }
    }
  return 0;
} 

y总的思路:

  • 基本上算是用时间换空间,加一个排序、查找
  • 对于每一个数,存储下这个数的数位和
  • 根据这个数位和对1~n进行排序
  • 最后只需查找出第m个位置的数

代码:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, m;
int w[N], s[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        w[i] = i;
        for (int j = i; j; j /= 10)
            s[i] += j % 10;
    }
    sort(w + 1, w + n + 1, [&](int a, int b) {
        if (s[a] != s[b]) return s[a] < s[b];
        return a < b;
    });
    printf("%d\n", w[m]);
    return 0;
}
//作者:yxc
//链接:https://www.acwing.com/activity/content/code/content/5088776/
//来源:AcWing
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

提示: 对于这道题的数据范围,如果在排序的同时进行计算数位和,会使得计算量上升一个量级。因为最快的排序也需要O(nlogn)的时间复杂度,所以需要先存下所有数的数位和,不然会TLE。

相关文章
|
机器学习/深度学习 自然语言处理 达摩院
Modelscope 工程介绍及实战演示| 学习笔记
快速学习 Modelscope 工程介绍及实战演示
Modelscope 工程介绍及实战演示| 学习笔记
|
存储 分布式计算 Java
JuiceFS分布式文件系统源码分析(Java层)
讲解了hadoop-common java api层面JuiceFS的实现流程
508 0
JuiceFS分布式文件系统源码分析(Java层)
|
API UED
逆向海淘代购集运系统方案:lete淘宝代购集运系统丨1688代采系统
**淘宝代购集运系统**整合多平台商品资源,提供代购、仓储、国际运输一站式服务。通过API接口实现商品实时同步,支持多种支付方式与国际物流,确保用户跨地域便利购物。系统涵盖订单管理、多语言支持、客服及营销功能,通过技术创新提升用户体验和满意度。关键点包括市场定位、支付物流体系构建、用户体验优化和API集成,助力海外用户轻松购买中国商品。
|
存储 NoSQL 安全
保障安全与可扩展性:Redis安全设置与集群扩展
本篇深入探讨了Redis的安全性设置以及构建可扩展的Redis集群的方法。我们首先介绍了如何通过设置密码、禁用危险命令和限制访问来加强Redis的安全性。进一步地,我们讨论了如何进行访问控制和权限管理,以确保只有授权用户可以访问和操作Redis。
972 2
保障安全与可扩展性:Redis安全设置与集群扩展
|
网络协议 Linux 网络安全
Linux配置SSH允许TCP转发
Linux配置SSH允许TCP转发
130 1
|
9月前
|
机器学习/深度学习 自然语言处理 算法
政府部门文档管理革新:实现90%自动内容抽取与智能标签化处理!
本文介绍了多模态数据处理技术,涵盖自然语言处理(NLP)、光学字符识别(OCR)和图像识别的技术原理,以及智能分类、标签化处理、系统集成与国产化适配、安全与合规、算法优化等方面的内容。通过这些技术的应用,实现了文档管理的全流程智能化,为用户提供高效、可靠的解决方案。
281 3
|
11月前
|
存储 Rust 搜索推荐
KaOS Linux 2024.09 发布
【10月更文挑战第6天】
226 2
KaOS Linux 2024.09 发布
|
11月前
|
机器学习/深度学习 人工智能 搜索推荐
AI在医疗诊断中的应用与未来发展趋势分析
【10月更文挑战第9天】 本文深入探讨了人工智能(AI)在医疗诊断领域的现状及其应用,包括影像识别、临床数据处理及个性化治疗方案的制定。通过具体案例分析,展示了AI技术如何提高诊断准确性、缩短诊断时间,并减轻医生的工作负担。同时,本文还讨论了AI在医疗诊断中面临的伦理问题和法律障碍,以及解决这些问题的可能途径。最后,对AI在未来医疗行业中的发展潜力进行了展望,指出其在提升医疗服务质量和效率方面的巨大潜力。
890 2
|
存储 人工智能 供应链
光量子计算:计算速度的新突破
【9月更文挑战第17天】光量子计算利用光子的量子特性,突破传统计算瓶颈,展现强大信息处理能力。本文阐述了光量子计算原理,聚焦“九章三号”新进展:255光子高斯玻色取样,性能超越现有超级计算机亿亿倍。同时,展望其在优化问题解决、量子模拟、加密技术革新及人工智能加速上的应用前景,并讨论面临的挑战与未来技术发展的无限可能。
|
12月前
|
存储 SQL 关系型数据库
MySQL 的锁机制,那么多的锁,该怎么区分?
MySQL 的锁机制,那么多的锁,该怎么区分?
142 0