当前位置:   article > 正文

2021-12-30每日刷题打卡_给定两个整数数组,arr1、arr2,数组元素按升序排列; 假设从arr1、arr2中分别取出一

给定两个整数数组,arr1、arr2,数组元素按升序排列; 假设从arr1、arr2中分别取出一

2021-12-30每日刷题打卡

力扣——排序

1356. 根据数字二进制下 1 的数目排序

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同,则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

示例 1:

输入:arr = [0,1,2,3,4,5,6,7,8]
输出:[0,1,2,4,8,3,5,6,7]
解释:[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

先准备一个map容器mymap(这里要用map而不是unordered_map,因为map中的key是有序的,orderedmap是无序的),然后用位运算的方法求出二进制下数字1的数目,按照数目把数存入map中,然后对key下的数字进行排序(比如1的数目为2的有5,3,7;排序后是3,5,7)之后把数都存入另一个vector容器里,返回这个容器即可。

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        map<int,vector<int>>mymap;
        for(auto i:arr)
        {
            int num=i,ans=0;
            while(num)
            {
                if(num&1)ans++;
                num=num>>1;
            }
            mymap[ans].push_back(i);
        }
        vector<int>v;
        for(auto &i:mymap)
        {
            sort(i.second.begin(),i.second.end());
            for(auto j:i.second)
            {
                v.push_back(j);
            }
        }
        
        return v;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
剑指 Offer II 075. 数组相对排序1122. 数组的相对排序

给定两个数组,arr1 和 arr2,

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例:

输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出:[2,2,2,1,4,3,3,9,6,7,19]

先准备一个map容器mymap,key为arr2中的元素,vul是出现次数,把arr2中的元素都存入mymap中,然后遍历arr1,如果mymap中有arr1的元素,则这个数的出现次数++,如果遇到了mymap中没有的元素,就把这个数存入vector容器里,当遍历完后对vector容器升序排序,准备一个vector容器v,根据arr2中元素的顺序和mymap中记录的出现次数把数存入v中,存完后把之前存在另一个vector容器里的数插入v中,最后返回v。

class Solution {
public:
    void quite_sort(vector<int>&nums,int l,int r)
    {
        if(l>=r)return;
        int x=nums[(l+r)/2],i=l-1,j=r+1;
        while(i<j)
        {
            do i++;while(nums[i]<x);
            do j--;while(nums[j]>x);
            if(i<j)swap(nums[i],nums[j]);
        }
        quite_sort(nums,l,j);
        quite_sort(nums,j+1,r);
    } 
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int,int>mymap;
        vector<int>v,v1;
        int n=arr2.size();
        for(auto i:arr2)
            mymap[i]++;
        for(auto i:arr1)
        {
            if(mymap[i]!=0)mymap[i]++;
            else v.push_back(i);
        }
        quite_sort(v,0,v.size()-1);
        for(int i=0;i<n;i++)
        {
            while(--mymap[arr2[i]])
                v1.push_back(arr2[i]);
        }
        for(int i=0;i<v.size();i++)
            v1.push_back(v[i]);
        return v1;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
1636. 按照频率将数组升序排序

给你一个整数数组 nums ,请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同,请你按照数值本身将它们 降序 排序。

请你返回排序后的数组。

示例 1:

输入:nums = [1,1,2,2,2,3]
输出:[3,1,1,2,2,2]
解释:‘3’ 频率为 1,‘1’ 频率为 2,‘2’ 频率为 3 。

准备两个map容器,一个根据数计算每个数的出现频率,一个根据上一个map容器获得的出现频率为key,把相同出现频率的数放在一起,然后对相同出现频率的数做降序排序,再把这些数都赋值回nums。

class Solution {
public:
    void quick_sort(vector<int>&v,int l,int r)
    {
        if(l>=r)return ;
        int x=v[(l+r)/2],i=l-1,j=r+1;
        while(i<j)
        {
            do i++;while(v[i]>x);
            do j--;while(v[j]<x);
            if(i<j)swap(v[i],v[j]);
        }
        quick_sort(v,l,j);
        quick_sort(v,j+1,r);
    }
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int,int>mymap;
        map<int,vector<int>>arr;
        int n=nums.size(),j=0;
        for(auto i:nums)
            mymap[i]++;
        for(auto i:mymap)
            arr[i.second].push_back(i.first);
        for(auto& i:arr)
        {
            quick_sort(i.second,0,i.second.size()-1);
            int m=i.first;
            for(auto k:i.second)
            {
                for(int l=0;l<m;l++)
                {
                    nums[j++]=k;
                }
            }
        }
        return nums;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
791. 自定义字符串排序

字符串S和 T 只包含小写字符。在S中,所有字符只会出现一次。

S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说,如果S中x在y之前出现,那么返回的字符串中x也应出现在y之前。

返回任意一种符合条件的字符串T。

示例:
输入:
S = “cba”
T = “abcd”
输出: “cbad”
解释:
S中出现了字符 “a”, “b”, “c”, 所以 “a”, “b”, “c” 的顺序应该是 “c”, “b”, “a”.
由于 “d” 没有在S中出现, 它可以放在T的任意位置. “dcba”, “cdba”, “cbda” 都是合法的输出。

先准备一个map容器,以字符为key,出现次数为vul,遍历T,把T中字符的出现次数都记在map中,然后遍历S,根据S中的元素顺序和map中的出现频率把字符添加到新准备的字符串str中,每插入一个字符,这个字符的出现次数–,为0时停止插入。然后当S遍历完后,把不出现在S中的字符都统一放在str的末尾。最后返回str。

class Solution {
public:
    string customSortString(string order, string s) {
        unordered_map<char,int>mymap;
        for(auto i:s)
            mymap[i]++;
        s.clear();
        for(auto i:order)
        {
            while(mymap[i]--)
                s+=i;
        }
        for(auto& i:mymap)
        {
            int m=i.second;
            char c=i.first;
            for(int j=0;j<m;j++)s+=c;
        }
        return s;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/615579
推荐阅读
相关标签
  

闽ICP备14008679号