解码方法
程序员文章站
2022-05-13 19:25:32
...
问题描述:
给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的n个自然数组成的多重集S,计算S的众数及其重数 。
1、常规思路
public void mode(int[] input)
{
// 先对输入数组进行判断
if (input == null || input.length == 0)
return;
// 排序
Arrays.sort(input);
HashMap<Integer, Integer> counts = new HashMap<Integer, Integer>();
// 统计每个元素的出现次数
for (int i=0; i<input.length; i++)
{
if (!counts.containsKey(input[i]))
counts.put(input[i], 1);
else
counts.put(input[i], counts.get(input[i])+1);
}
// 找到出现次数最多的元素(打擂台)
Set<Integer> keys = counts.keySet();
int maxValue = 0x80000000;
int maxKey = 0x80000000;
for (int key : keys)
{
int val = counts.get(key);
if (maxValue <= val)
{
maxValue = val;
maxKey = key;
}
}
System.out.println(maxKey + "出现次数最多,出现"+ maxValue+"次");
}
2、分治法
int start = 0, end = 0; // 表示最左、最右中位数的下标
int num = -1; // 出现次数最多的数,默认是-1
int largest = Integer.MIN_VALUE; // 最大重数
// 主函数
public void solve(int[] input)
{
Arrays.sort(input);
mode(input, 0, input.length-1);
System.out.println(num +": "+largest);
}
public void mode(int[] input, int l, int r)
{
int med = median(input, l, r); // 原数组中元素的中位数
int medCount = count(input, l, r); // 中间数的重数
// 找到出现次数更多的数,就更新
if (largest < medCount)
{
num = med;
largest = medCount;
}
System.out.println("num: "+num + "largest: "+largest + " medCount: "+medCount);
// 数组input[l, start)中可能存在众数
if (start-l > largest)
mode(input, l, start-1); // 1 2 2 2 3 5
// 数组input(end, r)中可能存在众数
if (r-end > largest)
mode(input, end+1, r);
}
// 查找input[left..right]之间的中间数
int median(int[] input, int left, int right)
{
// 找中位数
int med = (left + right) / 2;
return input[med];
}
// 统计中间数的出现次数
int count(int[] input, int left, int right)
{
int count = 0;
int m = (left + right) / 2;
int i = 0;
// 查找中位数的最左下标
for (i=left; i<=right; i++)
{
if (input[i] == input[m] )
{
count++;
start = i;
break;
}
}
// 查找中位数的最右下标
for (int j=i+1; j<=right; j++)
{
if (input[j] == input[m] )
{
count++;
end = j;
}
}
return count;
}
上一篇: android第一行代码学习笔记——activity
下一篇: 归并排序