藍橋杯 基礎練習 Huffman樹 Java實作

基礎練習 Huffman樹

試題

資源限制

時間限制：1.0s 記憶體限制：512.0MB

問題描述

Huffman樹在編碼中有着廣泛的應用。在這裡，我們隻關心Huffman樹的構造過程。給出一列數{pi}={p0, p1, …, pn-1}，用這列數構造Huffman樹的過程如下：

　　1. 找到{pi}中最小的兩個數，設為pa和pb，将pa和pb從{pi}中删除掉，然後将它們的和加入到{pi}中。這個過程的費用記為pa + pb。

　　2. 重複步驟1，直到{pi}中隻剩下一個數。

　　在上面的操作過程中，把所有的費用相加，就得到了構造Huffman樹的總費用。

　　本題任務：對于給定的一個數列，現在請你求出用該數列構造Huffman樹的總費用。

例如，對于數列{pi}={5, 3, 8, 2, 9}，Huffman樹的構造過程如下：

　　1. 找到{5, 3, 8, 2, 9}中最小的兩個數，分别是2和3，從{pi}中删除它們并将和5加入，得到{5, 8, 9, 5}，費用為5。

　　2. 找到{5, 8, 9, 5}中最小的兩個數，分别是5和5，從{pi}中删除它們并将和10加入，得到{8, 9, 10}，費用為10。

　　3. 找到{8, 9, 10}中最小的兩個數，分别是8和9，從{pi}中删除它們并将和17加入，得到{10, 17}，費用為17。

　　4. 找到{10, 17}中最小的兩個數，分别是10和17，從{pi}中删除它們并将和27加入，得到{27}，費用為27。

　　5. 現在，數列中隻剩下一個數27，構造過程結束，總費用為5+10+17+27=59。

輸入格式

輸入的第一行包含一個正整數n（n<=100）。

　　接下來是n個正整數，表示p0, p1, …, pn-1，每個數不超過1000。

輸出格式

輸出用這些數構造Huffman樹的總費用。

樣例輸入

5

5 3 8 2 9

樣例輸出

59

實作思路

/*
		Scanner in = new Scanner(System.in);
		int cnt = in.nextInt();
		Integer[] num = new Integer[cnt];
*/
//參數num數組存儲輸入的數列
//numMin主要實作找到num[]中最小的兩個數并使其相加
public static int sumMin(Integer[] num) {
		//x, y儲存num[]中最小的兩個數, 故賦一個較大的初值（其中x為最小數，y為次小數）
		//iX, iY則儲存兩個最小數的索引
		int i = 0, x = 100000, y = 100000, iX = 0, iY = 0;
		//周遊num[]
		while(i < num.length) {
			//目前的非零數小于最小數時，則使x的值變為次小數，目前數變為x的值
			if(num[i] < x && num[i] != 0) {
				int tmp = x;
				x = num[i];
				y = tmp;
				tmp = iX;
				iY = tmp;
				iX = i;
			}else if(num[i] < y && num[i] != 0) {
				y = num[i];
				iY = i;
			}
			i++;
		}
		//用num[iX]儲存最小兩個數的和，同時對num[iY]賦0，表示為空
		num[iX] = x + y;
		num[iY] = 0;
		return num[iX];
	}
           

完整代碼

import java.util.Arrays;
import java.util.*;
import java.util.Scanner;
import java.math.*;
public class Main {
	public static int cnt = 0;
	public static void main(String[] args) {
		Question();
	}
	public static void Question() {
		Scanner in = new Scanner(System.in);
		int cnt = in.nextInt(), i;
		Integer[] num = new Integer[cnt];
		int res = 0;
		for(i = 0; i < cnt; i++) {
			num[i] = in.nextInt();
		}
		for(i = 0; i < cnt - 1; i++) {
			res += sumMin(num);
		}
		System.out.println(res);
	}
	public static int sumMin(Integer[] num) {
		int i = 0, x = 100000, y = 100000, iX = 0, iY = 0;
		while(i < num.length) {
			if(num[i] < x && num[i] != 0) {
				int tmp = x;
				x = num[i];
				y = tmp;
				tmp = iX;
				iY = tmp;
				iX = i;
			}else if(num[i] < y && num[i] != 0) {
				y = num[i];
				iY = i;
			}
			i++;
		}
		num[iX] = x + y;
		num[iY] = 0;
		return num[iX];
	}
}