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

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

今天想練習的是演算法書本作者在求職面試上常常會考的一道題,作者的期望是一個正確的演算法實作,時間複雜度是甚麼?有沒有考慮過存在一個 O(n)時間複雜度的演算法。而作者提到很多求職者都知道自己的演算法是O(n2)時間複雜度,但是都否認存在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();
	}

}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

*

驗證碼 * Time limit is exhausted. Please reload CAPTCHA.

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料