Re: [闲聊] 每日leetcode

楼主: sustainer123 (caster)   2024-06-06 13:42:36
※ 引述《oin1104 (是oin的说)》之铭言:
: ※ 引述 《SecondRun (南爹抠打)》 之铭言:
: :  
: : 846. Hand of Straights
: :  
: : 给定一整数阵列和分组大小
: : 回传可否把数字分组,每一组的数字要连续
: :  
: : Example 1:
: : Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
: : Output: true
: : Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
: :  
: : Example 2:
: : Input: hand = [1,2,3,4,5], groupSize = 4
: : Output: false
: : Explanation: Alice's hand can not be rearranged into groups of 4.
: :
: 思路 :
: 反正一定是要每一个数字都用来排他的卡组
: 先看能不能整除
: 然后就把每个数字都塞进map
: 因为要有序
: 所以就每一次都拿最小的数字组成卡组
: 然后删除他们
: 如果可以组成的话就 可以
: 不行就return false
: class Solution {
: public:
: bool isNStraightHand(vector<int>& hand, int groupSize)
: {
: int len = hand.size();
: if(len%groupSize != 0)return false;
: map<int,int> paper;
: for(int k : hand)
: {
: paper[k]++;
: }
: while(!paper.empty())
: {
: vector<int> now;
: for(auto it = paper.begin() ; it != paper.end() ; it ++)
: {
: now.push_back(it->first);
: it->second
作者: oin1104 (是oin的说)   2024-06-06 13:44:00
c++ 的map会帮你在插入的时候排序 原理不知道 反正很方便
楼主: sustainer123 (caster)   2024-06-06 13:46:00
我感觉能想办法省下来 因为我才16%省下这个就变O(N) 多排序就nlogn
作者: oin1104 (是oin的说)   2024-06-06 13:48:00
可是要让他有序的话 就一定要排 所以这个方法大概就这样惹 nlogn我跟你都是nlogn 八
楼主: sustainer123 (caster)   2024-06-06 13:52:00
你n吧 那两个循环都实质N假如我没理解错误的话 我C++很粪
作者: oin1104 (是oin的说)   2024-06-06 13:54:00
没八 我插入map的时候会是logn 插入n个所以是nlogn
楼主: sustainer123 (caster)   2024-06-06 13:55:00
啊 对欸 忘了插入本身就要成本不对 哈希表插入元素的时间复杂度不是1?
作者: oin1104 (是oin的说)   2024-06-06 13:57:00
好想插入灵梦 我插入灵梦都不需要成本 随便插的不是 map是红黑树做的 unordered map 比较像是哈希 因为它无序map有序 插入的时候排的 然后原理是红黑书
楼主: sustainer123 (caster)   2024-06-06 14:01:00
喔喔 原来
作者: yam276 ('_')   2024-06-06 14:22:00
你效率要用unordered_map

Links booklink

Contact Us: admin [ a t ] ucptt.com