舟山企业网站建设,先备案 做网站,怎么做点击图片进入网站,网站设计的原则有哪些题目传送门
题目描述
给你一个整数数组 arr #xff0c;请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下#xff1a;
序号从 1 开始编号。一个元素越大#xff0c;那么序号越大。如果两个元素相等#xff0c;那么它们的…题目传送门
题目描述
给你一个整数数组 arr 请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下
序号从 1 开始编号。一个元素越大那么序号越大。如果两个元素相等那么它们的序号相同。每个数字的序号都应该尽可能地小。
样例 思路
这是一道非常基础的题目只需学会正确使用sort()函数即可。我们构造一个类NUM定义及注释如下
struct NUM{int v; //原数组中当前元素的值int o; //原数组中当前元素的下标int new_v; //答案数组中当前元素的值bool operator(const NUM n)const{return v n.v;}
}num[100005];首先对num[100005]数组进行初始化
for(int i0;iarr.size();i){num[i].v arr[i];num[i].o i;
}然后对NUM进行两次排序。第一次排序使用NUM中重载的运算符保证新数组的中的元素为v的升序排序然后对new_v进行赋值
int temp 1;
num[0].new_v 1;
for(int i1;iarr.size();i){if(num[i].vnum[i-1].v) temp;num[i].new_v temp;
}第二次排序使用cmp函数保证新数组中的元素为o的升序排序然后将new_v依次添加到答案vector的尾部即可。
代码
#includealgorithm
using namespace std;
struct NUM{int v; //原数组中当前元素的值int o; //原数组中当前元素的下标int new_v; //答案数组中当前元素的值bool operator(const NUM n)const{return v n.v;}
}num[100005];
bool cmp(NUM a, NUM b){return a.o b.o;
}
class Solution {
public:vectorint arrayRankTransform(vectorint arr) {vectorint a;for(int i0;iarr.size();i){num[i].v arr[i];num[i].o i;}sort(num, numarr.size());int temp 1;num[0].new_v 1;for(int i1;iarr.size();i){if(num[i].vnum[i-1].v) temp;num[i].new_v temp;}sort(num, numarr.size(), cmp);for(int i0;iarr.size();i){a.push_back(num[i].new_v);}return a;}
};官方题解
传送门
排序哈希首先用一个数组保存排序完的原数组然后用一个哈希表保存各元素的序号最后将原属组的元素替换为序号后返回。
class Solution {
public:vectorint arrayRankTransform(vectorint arr) {vectorint sortedArr arr;sort(sortedArr.begin(), sortedArr.end());unordered_mapint, int ranks;vectorint ans(arr.size());for (auto a : sortedArr) {if (!ranks.count(a)) {ranks[a] ranks.size() 1;}}for (int i 0; i arr.size(); i) {ans[i] ranks[arr[i]];}return ans;}
};
