用二分法求众数

一、题目引发：

Description:

Mishka has got n empty boxes. For every i (1 ≤ i ≤ n), i-th box is a cube with side length a_i.

Mishka can put a box i into another box j if the following conditions are met:

i-th box is not put into another box;
j-th box doesn't contain any other boxes;
box i is smaller than box j (a_i < a_j).

Mishka can put boxes into each other an arbitrary number of times. He wants to minimize the number of visible boxes. A box is called visible iff it is not put into some another box.

Help Mishka to determine the minimum possible number of visible boxes!

理解一下就是：给定一串序列，至少要拆分成多少组互异的子序列。

进一步理解：等价于求众数的重数。

二、分治法求众数及其重数

算法描述：首先将序列排好序，取中间值，分别左右遍历得到最长连续子序列，设此长度为L。若左子区间长度大于L,则向左递归；若右子区间长度大于L,则向右递归；

算法实现：

代码：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<stdlib.h>
 5 const int maxn = 5000 + 10;
 6 int len[maxn];
 7 int targrt,cnt = -1;
 8 
 9 int compare(const void * a, const void * b)
10 {
11     return (*(int*)a - *(int*)b);
12 }
13 void split(int * len, int l, int r)
14 {
15     int mid = (l + r) / 2;
16     int i, j;
17     for (i = l; i <= mid; i++)
18     {
19         if (len[i] == len[mid])
20             break;
21     }
22     for (j = mid + 1; j <= r; j++)
23     {
24         if (len[j] != len[mid])
25             break;
26     }
27     if ((j - i) > cnt)
28     {
29         cnt = j - i;
30         targrt = len[mid];
31     }
32     if ((i - l) > cnt)
33         split(len, l, i - 1);
34     if ((r - j + 1) > cnt)
35         split(len, j, r);
36     return;
37 }
38 int main()
39 {
40     int n;
41     scanf("%d\n", &n);
42     for (int i = 0; i < n; i++)
43         scanf("%d", &len[i]);
44     qsort(len, n, sizeof(int),compare);
45     split(len, 0, n-1);
46     printf("%d",cnt);
47     return 0;
48 }

View Code

三、其他方法

还可以参照“桶”的思想，每个数字就是桶的编号，桶的内容就是该数的重数。但是这个数字可能很大，就要采用哈希的办法，这个方法以后再补充吧！

而且这题不用二分法也能过，采用依次遍历，时间复杂度为O(N)（二分法的时间复杂度为O(log(N))）,代码实现起来非常的简单

代码：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 5000 + 10;
 6 int a[maxn];
 7 
 8 int main()
 9 {
10     int n;
11     scanf("%d", &n);
12     for (int i = 0; i < n; i++)
13         scanf("%d", &a[i]);
14     sort(a , a + n);
15     int ans = 1, cnt = 1;
16     for (int i = 1; i < n; i++)
17     {
18         if (a[i] == a[i - 1])
19         {
20             cnt++;
21             if (cnt > ans)
22                 ans = cnt;
23         }
24         else
25             cnt = 1;
26     }
27     printf("%d\n", ans);
28 }

View Code

秒客网

用二分法求众数

相关文章