練習 － 數列中重覆出現的正整數

今天看演算法的書時，才發現自己在這方面只會一些簡單的演算法，所以設計出來的程式發覺都沒有很好的效率。所以，為了要學好演算法，今天開始學習和在這裹做一些筆記。

今天想練習的是演算法書本作者在求職面試上常常會考的一道題，作者的期望是一個正確的演算法實作，時間複雜度是甚麼？有沒有考慮過存在一個 O(n)時間複雜度的演算法。而作者提到很多求職者都知道自己的演算法是O(n²)時間複雜度，但是都否認存在O(n)時間複雜度的演算法。雖然題目很簡單，但也思考了一陣子才想到怎樣實現O(n)時間複雜度的演算法。

題目：有一個由若干正整數組成的數列，數列中的每個數都不超過32，已知數列中存在重複的數字，請給出一個演算法找出這個數列中所有重複出現的數。

輸入：輸入若干正整數，每個正整數範圍為1至32。

輸出：列出正整數數列內重複出現的數。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ArrayInteger32 {

	public ArrayInteger32() {
		List<Integer> numbers = new ArrayList<Integer>();
		System.out.println("請輸入正整數，範圍為1至32，輸入0結束");
		Scanner scanIn = new Scanner(System.in); // 輸入正整數
		int n = scanIn.nextInt();
		while (n != 0) {
			if(n < 1 || n > 32) {
				System.out.println("數值超出範圍");
			} else {
				numbers.add(n); // 加入正整數到數列
			}
			
			scanIn = new Scanner(System.in); // 繼續輸入下一個正整數
			n = scanIn.nextInt();
		}
		
		int count[] = new int[32];
		List<Integer> resultNumbers = new ArrayList<Integer>(); //存放重複數的數列
		String result = "";
		for (Integer number: numbers) {
		    if(count[number-1] < 1) {
		    	count[number-1]++;
		    } else {
		    	if(!resultNumbers.contains(number)) { //重複的數如不在該數列內，則加入至該數列
		    		resultNumbers.add(number);
		    		result += number + ", ";
		    	}
		    }
		}
		
		if(!result.equals("")) {
			System.out.println(result + "為數列重覆出現的數");
		} else {
			System.out.println("數列沒有重覆出現的數");
		}
	}

	public static void main(String[] args) {
		ArrayInteger32 arrayInteger32 = new ArrayInteger32();
	}

}