一【题目类别】
- 排序
二【题目难度】
- 简单
三【题目编号】
- 1331.数组序号转换
四【题目描述】
- 给你一个整数数组 arr ,请你将数组中的每个元素替换为它们排序后的序号。
- 序号代表了一个元素有多大。序号编号的规则如下:
- 序号从 1 开始编号。
- 一个元素越大,那么序号越大。如果两个元素相等,那么它们的序号相同。
- 每个数字的序号都应该尽可能地小。
五【题目示例】
-
示例 1:
- 输入:arr = [40,10,20,30]
- 输出:[4,1,2,3]
- 解释:40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。
-
示例 2:
- 输入:arr = [100,100,100]
- 输出:[1,1,1]
- 解释:所有元素有相同的序号。
-
示例 3:
- 输入:arr = [37,12,28,9,100,56,80,5,12]
- 输出:[5,3,4,2,8,6,7,1,3]
六【题目提示】
- 0 < = a r r . l e n g t h < = 1 0 5 0 <= arr.length <= 10^5 0<=arr.length<=105
- − 1 0 9 < = a r r [ i ] < = 1 0 9 -10^9 <= arr[i] <= 10^9 −109<=arr[i]<=109
七【解题思路】
- 利用排序+哈希
- 首先复制一份原数组,然后对原数组从小到大排序
- 然后对排序后的数组进行哈希,key为数组值,val为数组值对应的排序,这样就可以对数组值去重,且记录每个数组值对应的数组下标
- 最后遍历复制的数组,对于每个元素我们取出其排序后的位置,设置为当前值
- 最后返回复制的数组即可
八【时间频度】
- 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn), n n n为传入的数组的长度
- 空间复杂度: O ( n ) O(n) O(n), n n n为传入的数组的长度
九【代码实现】
- Java语言版
class Solution {
public int[] arrayRankTransform(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
for(int i = 0;i < n;i++){
temp[i] = arr[i];
}
Arrays.sort(arr);
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0;i < n;i++){
if(!map.containsKey(arr[i])){
map.put(arr[i], map.size() + 1);
}
}
for(int i = 0;i < n;i++){
temp[i] = map.get(temp[i]);
}
return temp;
}
}
- C语言版
typedef struct
{
int key;
int val;
UT_hash_handle hh;
}HashItem;
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int* arrayRankTransform(int* arr, int arrSize, int* returnSize)
{
int* sortArr = (int*)malloc(sizeof(int) * arrSize);
int* res = (int*)malloc(sizeof(int) * arrSize);
memcpy(sortArr, arr, sizeof(int) * arrSize);
qsort(sortArr, arrSize, sizeof(int), cmp);
HashItem *map = NULL;
for(int i = 0;i < arrSize;i++)
{
HashItem *temp = NULL;
HASH_FIND_INT(map, &sortArr[i], temp);
if(temp == NULL)
{
temp = (HashItem *)malloc(sizeof(HashItem));
temp->key = sortArr[i];
temp->val = HASH_COUNT(map) + 1;
HASH_ADD_INT(map, key, temp);
}
}
for(int i = 0;i < arrSize;i++)
{
HashItem *temp = NULL;
HASH_FIND_INT(map, &arr[i], temp);
res[i] = temp->val;
}
*returnSize = arrSize;
HashItem *cur, *temp;
HASH_ITER(hh, map, cur, temp)
{
HASH_DEL(map, cur);
free(cur);
}
free(sortArr);
return res;
}
- Python语言版
class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
n = len(arr)
temp = [0] * n
for i in range(0, n):
temp[i] = arr[i]
arr.sort()
map = {}
for i in range(0, n):
if arr[i] not in map:
map[arr[i]] = len(map) + 1
for i in range(0, n):
temp[i] = map[temp[i]]
return temp
- C++语言版
class Solution {
public:
vector<int> arrayRankTransform(vector<int>& arr) {
int n = arr.size();
vector<int> temp = arr;
sort(arr.begin(), arr.end());
unordered_map<int, int> map;
for(int i = 0;i < n;i++){
if(!map.count(arr[i])){
map[arr[i]] = map.size() + 1;
}
}
for(int i = 0;i < n;i++){
temp[i] = map[temp[i]];
}
return temp;
}
};
十【提交结果】
-
Java语言版
-
C语言版
-
Python语言版
文章来源:https://www.toymoban.com/news/detail-654566.html -
C++语言版
文章来源地址https://www.toymoban.com/news/detail-654566.html
到了这里,关于【LeetCode每日一题】——1331.数组序号转换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!