LeetCode每日一题——1331.数组序号转换

题目传送门

题目描述

给你一个整数数组 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 i=0;i<arr.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 i=1;i<arr.size();i++){if(num[i].v>num[i-1].v) temp++;num[i].new_v = temp;
}

第二次排序使用cmp函数，保证新数组中的元素为o的升序排序，然后将new_v依次添加到答案vector的尾部即可。

代码

#include<algorithm>
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:vector<int> arrayRankTransform(vector<int>& arr) {vector<int> a;for(int i=0;i<arr.size();i++){num[i].v = arr[i];num[i].o = i;}sort(num, num+arr.size());int temp = 1;num[0].new_v = 1;for(int i=1;i<arr.size();i++){if(num[i].v>num[i-1].v) temp++;num[i].new_v = temp;}sort(num, num+arr.size(), cmp);for(int i=0;i<arr.size();i++){a.push_back(num[i].new_v);}return a;}
};

官方题解

传送门

排序+哈希：首先用一个数组保存排序完的原数组，然后用一个哈希表保存各元素的序号，最后将原属组的元素替换为序号后返回。

class Solution {
public:vector<int> arrayRankTransform(vector<int>& arr) {vector<int> sortedArr = arr;sort(sortedArr.begin(), sortedArr.end());unordered_map<int, int> ranks;vector<int> 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;}
};