问题描述:
现在有一数组存放int型整数,数字有重复,且有一数字出现的频率超过了50%,请找出这个数字。
补充:主要考虑数据量很大的情况。
问题求解:
分析:
最直接的方法就是对数组中所有的数字排序,然后再扫描一遍,统计各个数字出现的次数,如果某个数字出现的次数超过一半,则输出这个数字。显然这个算法的时间复杂度是O(N * log2N + N)。
事实上,假如现在数组已经有序,那么数组中间的数字一定是这个要求的数字,所以根本不必扫描。此时算法的时间复杂度是O(N * log2N + 1)。那还能不能再简化一些呢?
我们看到,算法主要的消耗在排序这块,那能否跳过排序这个步骤呢?我们这样想,假如每次删除两个不同的数(不管包括不包括最高频数),那么,在剩下的数字里,原最高频数出现的频率一样超过了50%,不断重复这个过程,最后剩下的将全是同样的数字,即最高频数。此算法避免的排序,时间复杂度只为O(N)。
代码如下:
1 static int FindMostApperse(int[] num)
2 {
3 int candidate = 0;
4 int count = 0;
5 for (int i = 0; i < num.Length; i++)
6 {
7 if (count == 0)
8 {
9 candidate = num[i];
10 count = 1;
11 }
12 else
13 {
14 if (candidate == num[i])
15 count++;
16 else
17 count--;
18 }
19 }
20 return candidate;
21 }
这个算法体现了计算机科学中一种很普遍的思想,就是把一个问题转化为规模较小的若干个问题。分治、递归、贪心等都是基于这样的思想。转化的效率越高,转化之后问题的规模缩小的越快,则正题的时间复杂度越低。
扩展问题:
现在数组中没有出现频率一半的数字了,但有三个都超过了四分之一,找到他们。
分析:
与原问题一样,只要降低规模即可,每次去掉四个不相同的数字,一直重复,最后剩下的三个数字就是答案。
代码如下:
1 static int candiA = 0, candiB = 0, candiC = 0;
2 static void FindThreeMost(int[] num)
3 {
4 int countA = 0, countB = 0, countC = 0;
5 for (int i = 0; i < num.Length; i++)
6 {
7 if (countA == 0 || countB == 0 || countC == 0 )
8 {
9 if (countA == 0)
10 {
11 if (countB != 0 && num[i] == candiB)
12 countB++;
13 else if (countC != 0 && num[i] == candiC)
14 countC++;
15 else
16 {
17 candiA = num[i];
18 countA++;
19 }
20 }
21 else if (countB == 0)
22 {
23 if (countA != 0 && num[i] == candiA)
24 countA++;
25 else if (countC != 0 && num[i] == candiC)
26 countC++;
27 else
28 {
29 candiB = num[i];
30 countB++;
31 }
32 }
33 else if (countC == 0)
34 {
35 if (countA != 0 && num[i] == candiA)
36 countA++;
37 else if (countB != 0 && num[i] == candiB)
38 countB++;
39 else
40 {
41 candiC = num[i];
42 countC++;
43 }
44 }
45 }
46
47 else
48 {
49 if (num[i] == candiA)
50 countA++;
51 else if (num[i] == candiB)
52 countB++;
53 else if (num[i] == candiC)
54 countC++;
55 else
56 {
57 countA--;
58 countB--;
59 countC--;
60 }
61 }
62 }
63 }
此算法的时间复杂度仍为O(N),只是判断条件较多,欢迎大家拿出更简明的代码来讨论。
分享到:
相关推荐
编程之美,微软技术面试心得,适合需要面试的同学
金融数量分析——基于MATLAB编程
面向初中生Python编程的教学设计与实践研究——基于项目式教学视角
《Python编程之美——带你进入Python语言世界》课程设计大纲参考.pdf
C语言项目——网络通信编程.zip C语言项目——网络通信编程.zip C语言项目——网络通信编程.zip C语言项目——网络通信编程.zip C语言项目——网络通信编程.zip C语言项目——网络通信编程.zip C语言项目——网络...
多线程编程之二——MFC中的多线开发
Python爬虫编程基础5天速成——P13——文件处理(csdn)————程序
多线程编程之二——MFC中的多线程开发
LabView-图形编程-虚拟仪器-源码-测试测量
Delphi 5高级编程丛书之二Delphi 5高级编程——GUI编程
上海贝尔的,对编程风格上的一些建议,个人感觉受益不少,所以想和大家分享下
代码之美 ——《代码之美》中文版 ,发现编程中的美! 去发掘生活工作中的美!
快速上手linux网络编程tcp服务器(csdn)————程序
软件编程等级考试真题Scratch二级——2020年第四季度模拟题附答案
高性能计算之并行编程技术—— MPI并行程序设计
数控高级编程——宏程序高级教程数控高级编程——宏程序高级教程
三菱F1系列可编程控制器教程——F1系列可编程控制器基本编程指令doc,三菱F1系列可编程控制器教程——F1系列可编程控制器基本编程指令
高性能计算之并行编程技术—— MPI并行程序设计
面向接口编程详解(二)——编程实例.doc
精彩编程与编程技巧-趣味撞球——VB应用程序一例 ...