设计制作活动内容的原则,郴州seo网络优化,网络舆情监测中心具体做什么,黑帽seo是什么关注我——个人公众号#xff1a;后端技术漫谈我目前是一名后端开发工程师。主要关注后端开发#xff0c;数据安全#xff0c;网络爬虫#xff0c;物联网#xff0c;边缘计算等方向。原创博客主要内容Java知识点复习全手册Leetcode算法题解析剑指offer算法题解析SpringClo…关注我——个人公众号后端技术漫谈我目前是一名后端开发工程师。主要关注后端开发数据安全网络爬虫物联网边缘计算等方向。原创博客主要内容Java知识点复习全手册Leetcode算法题解析剑指offer算法题解析SpringCloud菜鸟入门实战系列SpringBoot菜鸟入门实战系列Python爬虫相关技术文章后端开发相关技术文章image前言最近看了好多数据结构文章但是数据结构拾遗系列迟迟憋不出主要原因是很多数据结构其实非常偏门不仅日常很难遇到学起来还涉及很多数学模型很难有快速的理解方法。本着女排“短平快”的精神先更新下剑指offer题解系列。众所周知《剑指offer》是一本“好书”。为什么这么说因为在面试老鸟眼里它里面罗列的算法题在面试中出现的频率是非常非常高的。有多高以我目前不多的面试来看在所有遇到的算法体中本书算法题出现的概率大概是60%也就是10道题有6题是书中原题如果把变种题目算上那么这个出现概率能到达90%。如果你是个算法菜鸡(和我一样)那么最推荐的是先把剑指offer的题目搞明白。对于剑指offer题解这个系列我的写作思路是对于看过文章的读者能够做到迅速了解该题常见解答思路(偏门思路不包括在内节省大家时间实在有研究需求的人可以查阅其它资料)思路尽量贴近原书(例如书中提到的面试官经常会要求不改变原数组或者有空间限制等尽量体现在代码中保证读者可以不漏掉书中细节)尽量精简话语避免冗长解释给出代码可运行注释齐全关注细节问题题目介绍数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次超过数组长度的一半因此输出2。如果不存在则输出0。解题思路方法一思路该方法改变了原数组。首先要得到一个推论那就是一旦有数字大于数组的一半那么排序后的数组的中位数肯定是这个数字那么我们就先找出这个数字。这种算法是受快速排序算法的启发。在随机快速排序算法中我们现在数组中随机选择一个数字然后调整数组中数字的顺序使得比选中的数字小的数字都排在它的左边比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2那么这个数字就是数组的中位数。如果它的下标大于n/2那么中位数应该位于它的左边我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2那么中位数应该位于它的右边我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程找到这个数字后再判断他是否符合条件(大于数组的一半)因为很有可能他是数组中出现次数最多的但是未必大于数组的一半。详细细节见代码注释。代码public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array.length0) { return 0; } int start 0; int length array.length; int end length-1; // 右移1位相当于除2效率更高 int middle length1; // 当前位置 int index Partition(array,start,end); // 直到取到中位数才是结果 while(index!middle){ if(indexmiddle){ index Partition(array,start,index-1); } else{ index Partition(array,index1,end); } } int result array[middle]; // 需要统计该数字个数必须要大于数组长度的一半才能算 int times 0; for(int i0;iflag){ end--; } swap(array,start,end); while(array[start]flag){ start; } swap(array,start,end); } return start; } private void swap(int[] array, int num1, int num2){ int temp array[num1]; array[num1] array[num2]; array[num2] temp; }}方法二两两消除思路该方法不改变原数组。如果有符合条件的数字则它出现的次数比其他所有数字出现的次数和还要多。在遍历数组时保存两个值times次数result当前数字遍历下一个数字时若它与之前保存的数字相同则次数加1否则次数减1若次数为0则保存下一个数字并将次数置为1。遍历结束后所保存的数字即为所求。之后还要再判断它是否符合大于数组的一半。详细细节见代码注释。代码public int MoreThanHalfNum_Solution(int [] array) { int length array.length; // 检测数组是否为空 if (length 0){ return 0; } // 初始化result和times参数 int result array[0]; int times 1; //遍历数组(由于初始化过所以直接从第二个数字开始) for(int i1;i方法三hashmap思路将数组中的数字依次遍历并写入hashmap中hashmap的值是该数字出现的次数并在每次循环中判断是否该数次数大于数组的一半若有直接返回数字否则遍历完数组返回0。代码思路简单代码略。总结三种方法时间复杂度都是O(n)关注我我是一名后端开发。主要关注后端开发数据安全爬虫等方向。微信yangzd1102Githubqqxx6661个人博客CSDNqqxx6661知乎Zhendong简书蛮三刀把刀掘金蛮三刀把刀原创博客主要内容Java知识点复习全手册Leetcode算法题解析剑指offer算法题解析SpringCloud菜鸟入门实战系列SpringBoot菜鸟入门实战系列Python爬虫相关技术文章后端开发相关技术文章个人公众号后端技术漫谈如果文章对你有帮助不妨收藏起来并转发给您的朋友们~
