36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

一道很有意思的题目，要求判断一个9阶矩阵是否是一个合法的数独，对于合法数独的判断规则，总结一下有三点:

1. 每行必须由1~9组成，且不重复
2. 每列必须由1~9组成，且不重复
3. 每个3*3的九宫格必须由1~9组成，且不重复

所以这道题的主要思路就是对每行每列和每个九宫格进行检查，并判断是否符合数独的条件即可。

所以我们需要三个布尔数组用于标记行,列,九宫格是否合法，如果我们发现某一个元素在某行或某列中出现了不止一次，则应该返回false,否则我们继续判断，代码如下：

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool rowValid[9][9]={false},colValid[9][9]={false},subBoardValid[9][9]={false};
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'){
                    int num=board[i][j]-'0'-1;
                    int k=i/3*3+j/3;/*如果第一格九宫格的编号为0,board[i][j]这个元素存在于第(i/3*3+j/3)个九宫格内*/
                    if(rowValid[i][num]||colValid[j][num]||subBoardValid[k][num])/*如果在未赋值之前就为true,则说明发生了重复*/
                        return false;
                    rowValid[i][num]=colValid[j][num]=subBoardValid[k][num]=true;/*如果未重复，则将其赋值为true*/
                }
            }
        }
        return true;
    }
};

202. Happy Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

一个定义新运算的问题，所谓“幸运数”的定义很简单，一个数各位的平方和组成一个新数字，对新数字计算平方和，如果为1，则是幸运数，否则继续运算。

题目要求我们对幸运数进行判断，那么如何判断呢？我们可以将要判断的数字的各位进行分离，然后计算平方和，再进行组合之后，判断其值是否为1.

但这个思路要实现起来比较麻烦，而且属于暴力破解，能不能总结出一个关于幸运数的一般规律呢？

我们可以在纸上模拟幸运数判断的过程，如果一个数在题目定义的计算过程中，某两次的结果是相同的且不是1，那么就说明出现了周期现象，也就是说这个数无论经过多少轮运算，都不会得到1这个结果，所以就不会是幸运数。

但还有一个问题需要解决，如果一个数不是幸运数，那么会不会出现周期无穷大的情况呢？如果出现了这种情况，那么上述算法就会出现错误，在讨论区我找到了这个问题的证明，原文证明非常详细，在此就不再赘述了，链接如下:

算法证明

证明得到的结论是，如果一个数不是幸运数，那么一定会有一个常数T，使得某两个间隔为T的运算结果相等。

所以我们的思路是:用一个unordered_set存储每一次的运算结果，如果该结果不在set中，则将其插入;若存在，则判断其是否为1，为1则是幸运数，否则不是。 代码如下:

/*solution1 use unordered_set,7ms*/
class Solution {
private:
    int divideThenSum(int n){
        int tmp=n,sum=0;
        while(n){
            tmp=n%10;
            sum+=tmp*tmp;
            n=n/10;
        }
        return sum;
    }

public:
    bool isHappy(int n) {
        unordered_set<int> hash;
        int res=n;
        while(true){
            res=divideThenSum(res);
            if(hash.count(res)==0)
                hash.insert(res);
            else
                return res==1;
        }
    }
};

AC之后又进行了更深一步的思考，既然是周期现象，那么也可以尝试一下Floyd Cycle Algorithm，即我们在判断链表是否有环时使用的算法(快慢指针法),代码如下:

/*solution 2,use Floyd cycle algorithm,4ms*/
class Solution {
private:
    int divideThenSum(int n){
        int tmp=n,sum=0;
        while(n){
            tmp=n%10;
            sum+=tmp*tmp;
            n=n/10;
        }
        return sum;
    }

public:
    bool isHappy(int n) {
        int slow=n,fast=n;
        do{
            slow=divideThenSum(slow);
            fast=divideThenSum(divideThenSum(fast));
        }while(slow!=fast);
        return slow==1;
    }
};

面对寒冬，创业者们应该怎样面对？

不要畏惧，就像小孩子总是经过一些摔打才会成长，这个行业的从业者们也总是只有经历了一些泡沫破灭和低谷后才会变得更加客观和理性。

对于优质、有价值的公司和产品而言，寒冬只是他们的蛰伏期而已。

文/黄有璨 转载自：三节课（ID：sanjieke） 腾讯创业已获得授权

本周四，36氪发布了一篇题为《裁员！裁员！裁员！创业者们的寒冬大逃杀》的专稿。

文章一出，瞬间在朋友圈形成刷屏之势，短短2小时，阅读量已10W+。此外，标题连用3个感叹号，对媒体专稿而言，也颇为少见。

可以明确感到，当前正在经历的这一轮“寒冬”，对于整个互联网行业和创业者们而言，是多么痛彻心扉感同身受。

在整个2016年，整个大环境确实正在变得越来越糟。烧钱、补贴、团队扩张、高薪挖人等等这些曾经在2015年上半年还是特别常见不过的事情，现在早已销声匿迹。

就亲眼所见，从2016年三四月份开始，我身边几乎每周都会听到至少一个团队和项目关停解散的消息，哪怕是很多已经走到了B轮的公司，也难逃劫数。

创业公司一片肃杀，一线从业者们也不好过。

就在今天，我刚刚见了一位朋友F，也是三节课的学员，她此前在一家O2O公司做产品，年初因为公司无以为继而离职，选择跳槽到某上市教育公司。但现在，3个月刚刚过去，她所在的公司又一次因为业务线调整而要经历裁员，而她所在的事业部，又一次成为了遭受打击的对象，她也再一次失业了。

F的经历，可能只是一个缩影。在2016年遭受到公司动荡和业务调整的互联网从业者们，我相信多不胜数——你可以想见，上市公司尚且如此，何况其它？

在与很多像F这样的朋友的交流中，我可以感受得到他们当下的不知所措和人心惶惶。

这篇文章，算是临时有感而发，我想结合当下我们正在经历的这个恶劣的大环境和一线互联网从业者们面前的一些疑惑和困境来聊聊一些感想+建议。

我就想到哪说到哪了。

◆ ◆ ◆ ◆ ◆

对3岁以内的互联网从业者而言，请尽量学会减少关注概念和大方向，转而更多思考“如何能够迅速积累起一项核心技能”，或是“如何成为一个领域内的专家”。

今天的交谈中，我有问过F：你当时离开那家O2O公司出来后，为啥突然就想到要去做教育呢？

她答：因为我感觉在线教育这个行业有前景啊！教育还没充分被互联网改变啊！

我继续往下问：教育的哪些分支内的哪些环节现在你觉得是可以被互联网改变的呢？

她有点答不上来。

F的状态，是典型的一种新人容易出现的问题——我们总是太容易被很多概念所消费，从而变得喜欢去关注概念和大方向这样宏观的东西，但如果你实际的从业经验连3年都不到，这个时候的你很可能是还不具备能力去理解和思考这些概念背后的一切的。

如果选择去相信和盲从于一个你自己并不能真正透彻理解的东西，其实往往会给自己带来伤害。

以我为例，2012年我第一次创业做教育和学习，当时也一样张嘴闭嘴谈概念，大谈“在线教育”的前景光明，大谈“平台”的价值等等。但当时的我，其实对于教育一窍不通，也完全不理解“平台”背后的运营逻辑究竟是怎样的，于是很顺理成章的，我们撞得头破血流。

从2013年下半年开始，我开始深刻意识到我对“教育”和“学习”的无知，于是，我开始回归到具体的问题中，去思考我想要做的是成人教育还是K12？是主动型学习还是被动型学习？以及我到底想要解决和能够解决的，是某个品类下现在用户学习动力不足的问题，是用户缺乏清晰学习路径的问题，还是学习过程中的互动和激励的问题，又或是最后的学习结果测评和认证的问题？

那之后，我才慢慢变得靠谱了许多。直到后来开始可以对教育领域内的很多产品拥有判断能力。

所以，概念和“趋势”等一类偏宏观的东西，我认为对于资历尚浅的从业者们其实意义不大，甚至很多时候可能会是负作用。与其把时间花在它们身上，可能不如去思考点儿更加实际的。

以F为例，我觉得以她的背景，其实可能最应该思考的，应该是“如何让我自己能够持续去向O2O这个行业深耕，让我对于这个行业可以拥有更多的理解、洞察和思考？”，又或者是“如何让我自己成为后端产品中的专家？”

相比于去看自己尚还判断不了的“大势”，这些东西可能对她而言，价值会更大。

◆ ◆ ◆ ◆ ◆

公司的靠不靠谱与你自己个人的职业生涯发展很可能并不完全相关，甚至是，你可能要尽量打破这种相关性。

上一个建议是奉劝大家不要看“大势”，我猜此时一定会有人跳出来说：你特么倒是说得轻巧，万一老子找了个公司，3个月不到又黄了，那岂不是很坑？

我来分享个我自己真实的故事——

2012年以前，我自己顶天还只算是执行力还不错的运营小白。2012年开始，我和几个朋友一起创业做了个不靠谱的项目，但项目虽然不靠谱，我却成功在2年左右的时间里找到了很多空间，在局部做出来了很多还不错的产出，比如说花不到2000块钱搞了个活动，拉了一万多注册用户；比如说牵头搞了个收入项目，带来了几十万收入，等等。

然后，当我有了这些经历之后，我发现，开始有成群结队的人主动向我示好，邀请我加入他们的团队。原因很简单，虽然我们的项目没做成，但我却已经在项目的局部充分展示了我的能力，并积累了资源与经验。

是的，确实有很多同学还处于这样的状态中，即：他们个人的职业发展当前与公司的发展和前景有着很强的相关性，一旦公司发展良好融资顺利，他们薪资水涨船高，但一旦公司流年不利，则他们会变得非常尴尬。

但我尤其想要提醒大家的是：如果你并不是那么命好可以正好进入到大公司内部的核心部门担任要职，你可能需要尽量摆脱自己对于“大公司”的依赖，无论是在行动上还是参与上。

而打破这种依赖最重要的一点转变可能在于——不再那么在意你要去什么公司，而更多开始在意你可能会负责和参与些什么项目，以及在这些项目中你可能能够获得哪些资源、经验和技能积累。

一旦你能够把心态调整到这种状态，我相信，哪怕你呆的公司不靠谱，你自己个人的成长也仍然一点都不会耽误。

◆ ◆ ◆ ◆ ◆

要学会相信一些更为长远的东西，而不是只一味看短期和眼前的回报。

人们都过于容易在短期诱惑面前妥协。但长线来看，往往却是那些拥有某种长期信念的人能够笑到最后。

我还清晰记得，在2014年下半年到2015年初那段整个行业最疯狂的时候，一大堆创业公司高薪挖人，造就了大量互联网人的薪资水涨船高，也让很多人变得不淡定。那个阶段，一个刚毕业的研发张嘴就要15K是很常见的事。

但站在今天回过头来看，恰恰是那批当时在整个失去理性的时候为了追求高薪而狮子大张口选择跳来跳去的人，成了今天这个大环境下最痛苦慌乱的人——一方面，薪资明显溢价的他们很容易会成为这轮裁员潮中首当其冲的牺牲者；另一方面，才处在职业生涯早期的他们，为了追求动辄double的薪资而进入到一个极度不稳定的环境中，这往往导致他们当中的大多数人，在过去1-2年内很难有亮眼的产出，甚至是很多原本天资不错的新人，可能连把自己的基本功和工作习惯变得足够扎实的机会和空间都没有。

于是，回过头来到现在，拿惯了高薪，职业变动频繁，且过去一两段履历中又缺乏亮点和产出的他们，在自己的求职和职业发展道路上，反而不知不觉就成为了“容易遭人嫌弃”的一群人。

相反，倒是一两年前那些看起来有点蠢笨，更加“耐得住寂寞”，踏实在自己的岗位和领域上认真积累了2、3年经验和资历，并已经让自己有了一点产出，职业生涯变动不那么频繁的人，现在可能成为了行业中更加具有竞争力的一群人。

我总是在跟很多人说，要学会相信一些长远，踏实的东西。虽然这很不容易，但最终你会发现，那些才是最重要的。

◆ ◆ ◆ ◆ ◆

如果你是一个靠谱的从业者，你最好能够学会去判断一家公司和一个老板是否靠谱。

如前所言，这已经是一个泡沫破碎的时代，所以再指着跟着一个“踩住风口”和“炒作概念”的公司去混几年然后就能拿走一笔钱的想法，基本已经不太能够成立了。

所以，对于一个至少有了3年以上经验的从业者来说，我觉得你最好能够学会判断和甄别靠谱的公司与不靠谱的公司，靠谱的老板和不靠谱的老板，尤其是对于去创业公司而言。

你可能无法完全规避创业公司会有的种种风险，但你至少可以选择靠谱的老板。请相信我，如果跟着一个靠谱的老板，哪怕最后项目和产品挂了，你也会有更大的可能性和空间能够去积累起来一些自己的核心竞争力。

具体来说，如果你问一个老板“你为什么能在这个领域成功”，发现他的回答基本只是一些行业大势和概念的话，这个老板八成不怎么靠谱。

而如果你发现一个老板给你的回应能够具体到他在这个行业已经工作了XX年，已经积累了XX资源，当前这个行业的产业链格局是怎样怎样的，哪个环节存在着痛点，也许可以如何解决等等，这样的老板可能会更靠谱，更值得你跟一点。

◆ ◆ ◆ ◆ ◆

最后，也不妨试着看得更宏观一点——这轮寒冬短期看虽然很悲惨，但长期看，对整个行业一定是好事。

从2010年前后开始至今，其实我们所见证的，是一场“大众创业”热潮在国内的从兴起到退潮。客观意义上讲，这是国内第一次经历“大众创业”热潮的洗礼。

既然是第一次，必定会伴随着诸多不理性、不冷静、浮躁的东西，从资本到行业到创业者再到一线从业者，莫不如是。

我还记得，2011年前后我刚刚开始混迹车库咖啡等创业咖啡馆的时候，大家张嘴闭嘴都是“社交2.0”，然后，他们开始谈“互联网医疗”和“在线教育”，再后来，人们更热衷的话题变成了“社群经济”和“网红经济”，人们总是张嘴闭嘴就说“这是一个千亿美金级的市场”。

甚至，后来这种风气也蔓延到了很多从业经验尚浅的互联网人身上，他们也可以张口闭口三句不离概念。

但，就像小孩子总是经过一些摔打才会成长，这个行业的从业者们也总是只有经历了一些泡沫破灭和低谷后才会变得更加客观和理性。就像我们前面提到的，在这轮资本寒冬里活下来的一群公司和产品，可能就真正是一些优质、有价值的公司和产品了。而在这样的背景下所能活下来的创业者们，也一定更加隐忍和潜力巨大。

对于这样一群人而言，我相信寒冬只是他们的蛰伏期而已。假以时日，他们身上必会爆发出更大的能量，而这群人得存在，也一定会让整个行业变得更加健康、积极和理性。

一个大家都不再一味热衷于“社群经济”、“网红经济”等概念，而是转而更多思考类似“社群到底是不是一个可以被标准化和可被复制的模式？”，“存不存在一种标准的产品形态可以用于支撑它的发展？”，“它的存在，到底帮助用户解决了什么问题？”这些核心问题的互联网，会是我更加愿意看到的。（完）

昨天焦虑地一夜没睡好，忙得根本没空写公众号 发一篇去年说焦虑的文章，不知你们有没有共鸣

01

几个月不见，认识的某姑娘做大V月收入就从60万一直涨到了200万，不仅开上了之前就心心念的保时捷，还在上海内环买了房，说是等装修完毕后请我们都去她家玩，一时风光无限。看着她依然在朋友圈甜甜笑着卖着萌，就连原先最讨厌她的那些人都不得不赞叹姑娘不卑不亢的态度。

这让我常常看着自己工资卡里那点可怜的数字叹气。虽然对这个朋友起不了嫉妒之心，但还是忍不住做各种各样以“如果我”开头，以“就好了”结尾的假设——结果当然是毫无意义，反而常常令我想起四年前和她一起在深夜撸串哭穷的样子，感觉像是已经过了一个世纪。

比起跨越阶级往往需要几代人努力的历史，这也确实是一个世纪。

02

对这个时代来说，四年足够让一个人从一文不名到家财万贯：

只要你在2003年赶上大潮，在淘宝网上开设一家店铺，并用心经营下去，那你现在少说有一家流水过千万的店铺。

只要你在2004年在北京二环内买上两套房子，然后在4年后卖出去，至少一千万在手，光靠吃利息至少十年不用愁。

开个玩笑的说，只要你从2005年起，拿出一千块，每逢中国队踢足球就拿出一半压他输，那你也腰缠万贯，至少不用再为生计担忧。

不仅如此，05年开始写博客的，09年开始玩微博的，12年开始弄微信的现在无一不是大V，往小了说，年入百万不是什么大问题。

36kr的创始人刘成城曾经在一次采访中这样说道：

“当时微信还是一个很小的团队，但是我们对它很有信心，主动为他们做了很多报道，建立起了深厚的革命友谊，所以，微信公众号内测的时候我们就受邀加入了内测。不仅获得了一天可以发布10次内容的特权，而且第一天就获得了10万多名粉丝。”

如今，36氪的估值已经超过35亿人民币，甚至远远不止。

时间和节奏明显变快了，以往一个公司从无到有再到飞黄腾达往往要经过一代人的时间。而对80，90这一代人来说，四年的时间已经完完全全够一家公司从创业团队到全中国同行业最大，比如说手机界的小米。

这样的社会早已不相信按劳分配，暴走的资本和飞奔的信息流连通起了整个世界，它们借着互联网的势把世界从一片广阔踏实的土地变成一片四处都是大浪的汪洋。在那汪洋的高峰处，有人躺在暴利行业里赚取这个社会百分之八十的财富，而汪洋的低谷处，也有人孤注一掷，摔个粉碎，不知何时才能重抵高峰。但至少这个时代创造了无数机会，为阶层流动创造了可能性，这是最好的时代。

然而我们大多数人根本不知道下一个到达高峰的行业是什么，甚至不知道这个社会已经不相信按劳分配，不知道在某些错误的行业，就是努力一辈子，也只是在泥潭里挣扎，完全实现不了我们内心渴望的财务自由。或在茫茫就业市场前彳亍不前，或最后妥协，选了自己最不喜欢的一个行业受了一肚子气。

有的人一失足成千古恨，这也是最坏的时代。

85后，90后，95后甚至98年的妹子纷纷被资本和媒体捧上神坛：

然后再被狠狠得扔到脚下：

从无到有再到无，一共只有半年的时间，或者干脆在茫茫就业市场前彳亍不前，焦虑不已。

不知道自己未来在何方。

03

有人把焦虑症称之为中国这一代人的时代病：

看电影只能去电影院，不然就只能快进；玩社交网络一分钟要刷新十几次，每次刷新看不到别人回复自己就浑身难受；评论要抢沙发，创业要一夜暴富。酒量结婚也最好是有车有房，什么都不用烦。之前中青报做过一项针对青年白领的调查，调查称百分之34的人经常焦虑，百分之62.9的人偶尔焦虑，而只有百分之0.8的人表示从来没有焦虑过。

之前群里有个90后自媒体人这样问道： “想请问，没有安全感，老是感到焦虑，跟从小的生长环境有关吗？” “我总觉得自己做不好事情，不知道为什么。”

而我这样答道： “因为你周围总有人不停告诉你他们做的有多好，不焦虑才有鬼了。”

她好像突然领悟到什么，在朋友圈里写下了这样一行字： “每天一大堆人和我说他们两个月十万粉的故事，快把我逼疯了。“ ”焦虑就快把我逼疯了！” 那时我正在健身房，摸着自己的肚子，看着周围帅哥们健美的肉体，默默地给她这条朋友圈点了个赞。

是啊，我们错过了淘宝皇冠店铺，错过了博客名博主，微博KOL，微信朋友圈大V，错过了2001年加入阿里巴巴，2002年去做房地产房地产，错过了做手机游戏，股市神话，创业大潮——而且我们不知道未来还会错过什么。而且看看周围，上司比你年轻，新来的同事都是95后。打开朋友圈好像所有人都创业成功了，再跑去书店看到每一本书都像在告诉你应该怎么成功。

好像这个世界上的每个人都比你有钱，比你帅还比你努力。这些人生赢家就在你身边，每时每刻都在提醒你： “你已经被社会淘汰，是个失败者！” “你已经被社会淘汰，是个失败者！” “你已经被社会淘汰，是个失败者！”

而你和我一样，租着房子，坐着地铁，朝九晚不知道几点的为了生计奔波。不知道自己的未来究竟在什么地方，不知道这种日子什么时候是个头。

生活中好像处处是机会，但是我们似乎永远要等到机会已经过去才能发现它们。当“如果当初我xxx就好了”这样的句式多起来的时候。

又怎么能不焦虑呢？

都不想庸常，但也只能庸常

04

在2013年单独二胎政策开始实行后的两年，国家终于意识到中国人口老龄化，倒挂现象越来越严重的问题，准备全面放开二胎政策。全面放开二胎政策后，我们80后，90后乃至00后这30年的一代人竟然成了中国五千年历史上唯一一代独生子女，而这三十年年恰好是中国经济腾飞，与世界接轨，变化最大的三十年。

于是纵向上，我们父母陈旧的经验没办法给我们帮助，我国陈旧的教育体系又常年与横向上，作为独生子女的我们又比别的国家的这一代人承担更多期望，当然也有更多压力。

没有人教导，没有人倾诉。身上担满了压力，周遭总是令人焦虑——所以我们注定在孤独中长大，而我们的孤独也注定无处诉说。无论是父母生病还是配偶离去，每一项都可能成为压垮我们身上重担的最后一根稻草。

又何止是80后，又何止是四个父母，两个孩子

就像现在已经没有人再提网瘾了一样，你看现在是不是也没有人再提啃老了。

因为看着北京上海动辄4万，5万一平米，市中心10万起跳的房价，榨干双方父母一辈子的积蓄，以求在大城市买到一套房子，为了让自己的下一辈在教育，医疗，工作，高考等领域获得真正的公平已经成为外地人的必然选择。而且绝大多数人是榨干了二老的积蓄后还要搭上大半辈子用来还贷。

看看北京上海的高考录取率，人均收入，以及一套房子一千万的不动产价值，你会发现这就是赤裸裸的阶级。如果你处于靠下的阶级就是要被歧视，就是要焦虑。没有别的选择。

05

上周末看了上海戏剧学院的同学排的一出话剧，名字叫做《庸常》。那个学生导演可能用尽了自己在课上学过的所有戏剧表现形式，尽力表现出一个不愿意过庸常生活的女作家的庸常生活。

这常常让我想到四年前和我那个如今已是白富美的朋友哭穷撸串时的对话。

那会儿她刚从某个只知道讲情怀很少发工资的公司逃出来，几乎身无分文的投奔我，而我正翻译完一本德语书，领了少得可怜的翻译费还上之前借同学的几百块钱。

她说她焦虑的要命，问我要不要去报个培训班学程序，一个月能挣8000块钱。我摇摇头说我也不知道，就带着她在佘山，辰山玩了一圈。到了晚上吃宵夜时，我们一边撸串喝酒一边大声吹牛逼。

当时有辆红色的保时捷911从人民北路边呼啸而过，发出巨大的动静。于是她就红着眼睛问我信不信她以后也能开这么辆车，五年后就开得上。

因为喝了太多酒，我们最后谁也记不得之后我说了什么，只记得喝醉的最后，我们在回去的路上一起唱了李志的一首歌：

不知道有谁能让你述说 你这样的生活到底为了什么 我看见你靠在窗口沉默 路过了青春我们还拥有什么 这让人心慌 这让人心慌 这让人心慌 这让人心慌

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

这道题要求我们在O(n log n)的时间复杂度内，返回一个数组中出现次数最多的k个元素，要求复杂度小于O(nlogn)，这道题的难度主要在时间复杂度的要求比较严格上，思路如下:

哈希表+堆

这道题可以转化为对数组中各个元素的出现次数进行统计，之后从这个次数的序列中找到前k大的元素，那么要解决寻找前k大的元素的问题，我们有了之前的经验，应该选用堆这种数据结构，而且应该是小顶堆。

确定前k大的元素的思路和378. Kth Smallest Element in a Sorted Matrix基本一致，代码上稍作了一些修改，代码如下:

时间复杂度为O(nlogk)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        vector<int> res;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;/*第一个参数指定元素类型，第二个参数决定使用哪一种容器，
																						第三个用于建立小顶堆*/
        for(auto num:nums)
            hash[num]++;
        for(auto pos : hash){
            heap.push({pos.second,pos.first});
            if(heap.size()>k)
                heap.pop();
        }
        while(!heap.empty()){
            res.push_back(heap.top().second);
            heap.pop();
        }
        return res;
    }
};