拍照搜题秒出答案,一键查看所有搜题记录
拍照搜题秒出答案,一键查看所有搜题记录
拍照搜题,秒出答案一键查看所有搜题记录
算法--找出一个大于给定整数数组Φ出现次数超过一半的数
每当我看到经典的算法题就怀念高中,感觉很多算法题就是高中的题目谁叫哥只读了个专科,高数基本相当沒学
第一个想到的方法是见一个二维数组,一维存数组中的数据二维存这个数出现的次数。出现次数最多的那个数就是要找的那个数
甴于某个数出现的次数超过数组长度的一半所以二维数组的长度只需要这个数组的一半。代码实现如下
当然这个方法很糟糕,时间复雜度和空间复杂度都比较大想练手的我还是写了一下。
如果不是最小也不是最大当这个数由最小慢慢变成最大的最大的数时,你会发現中间的那个数的值是不变的
时间复杂度就是你排序用的时间。排序真的不想写了(可以参考《》)大家都知道排序还是相当费时的,当然这个方法还是不太好
开始时k存储数组中的第一个数,j为0,如果数组出现的数于k相等则j加1,否则就减1如果j为0,就把当前数组中的數赋给k
因为指定的数出现的次数大于数组长度的一半所有j++与j--相抵消之后,最后j的值是大于等于1的k中存的那个数就是出现最多的那个数。
下面这个算法只适合数组中数组中某个数的出现次数超过数组长度一半的数组符合题意。