今天看演算法的書時,才發現自己在這方面只會一些簡單的演算法,所以設計出來的程式發覺都沒有很好的效率。所以,為了要學好演算法,今天開始學習和在這裹做一些筆記。
今天想練習的是演算法書本作者在求職面試上常常會考的一道題,作者的期望是一個正確的演算法實作,時間複雜度是甚麼?有沒有考慮過存在一個 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(); } }
鏈結到這頁!