当前位置:网站首页>Maximum number less than n
Maximum number less than n
2022-07-27 17:19:00 【Folded cookies】
Give an array nums=[5,4,8,2], Give me a n=5416, Let you nums Select some elements , Make the composition number less than n The maximum number of
Ideas : greedy + Two points search
Traverse n The number on each of you , Find the highest order of a number that does not exist in the array
This bit did not change before , This bit is changed to less than n The maximum value of this bit of , The rest are nums Maximum in
If all exist , Then modify the lowest order
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Find less than idex The last one of
int searchl(vector<int>nums,int target){
int l=0,r=nums.size()-1;
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]<target)l=mid;
else r=mid-1;
}
if(nums[l]<target)return nums[l];
else return -1;
}
// Find less than or equal to idex The last
int searchle(vector<int>nums,int target){
int l=0,r=nums.size()-1;
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]<=target)l=mid;
else r=mid-1;
}
if(nums[l]<=target)return nums[l];
else return -1;
}
int main(){
vector<int>nums={
1,1,1};
int n=1234;
vector<int>maxn,ans;
sort(nums.begin(),nums.end());
while(n){
maxn.push_back(n%10);
n/=10;
}
int len=maxn.size();
int h=len;
for(int i=len-1;i>=0;i--){
int idx=searchle(nums,maxn[i]);
// printf("maxi=%d,idx=%d\n",maxn[i],idx);
if(idx!=maxn[i]){
h=i;
break;
}
}
if(h>=0){
for(int i=len-1;i>=0;i--){
if(i>h)ans.push_back(maxn[i]);
else if(i==h)ans.push_back(searchl(nums,maxn[i]));
else ans.push_back(nums[nums.size()-1]);
}
}else{
for(int i=len-1;i>=1;i--){
ans.push_back(maxn[i]);
}
ans.push_back(searchl(nums,maxn[0]));
}
for(int i=0;i<ans.size();i++){
printf("%d\n",ans[i]);
}
return 0;
}
边栏推荐
猜你喜欢

诸神黄昏,“猫抖快”告别大V时代

Bit band operation of semaphore protection

Two table joint query 1

Measured: the performance of cloud RDS MySQL is 1.6 times that of self built

Neural network implementation of handwritten numeral classification matlab

Shardingsphere-proxy-5.0.0 distributed snowflake ID generation (III)

Functions in JS

三表联查3

meta-data 占位符的引用

关于 SAP UI5 应用 ui5.yaml 里的 paths 映射问题
随机推荐
Three table joint query 2
Kubernetes Part 7: using kubernetes to deploy prometheus+grafana monitoring system (kubernetes work practice class)
Program environment and preprocessing of C language
Swift QQ授权登录 坑集
从零开始Blazor Server(1)--项目搭建
小于n的最大数
三表联查2
Understand the basic properties of BOM and DOM
App Crash收集和分析
一个端到端的基于 form 表单的文件上传程序,包含客户端和服务器端
Redis: 配置AOF不起作用
Three table joint query 3
第7天总结&作业
深度学习能颠覆视频编解码吗?国家技术发明奖一等奖得主在小红书给你唠
下棋机器人折断7岁男孩手指,网友:违反了机器人第一定律
格力「不清凉」:巨头诉讼落幕又遭大经销商减持,空调新战场还晚人一步?
Complete steps of JDBC program implementation
国产新冠口服药为什么是治艾滋病的药
2021-06-18 SSM项目中自动装配错误
ES6 array method and pseudo array to array method