欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

解码方法

程序员文章站 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;
	}
	

 

相关标签: 分治法