題目

題目的意思是，找到第一個不重復的元素。輸出它。

一開始用Java做，試了好多種方法都超時。后來換用C++通過了。

---

AC題解：C++版

用Java嘗試了各種方式，都是后兩個測試點過不去，只好換C++

這個算法挺巧妙的，注意記錄輸入順序的方式

#include <iostream> using namespace std; int main() {int num[100001], count[10001];int n;cin >> n;for ( int i = 0; i < n; i++ ){cin >> num[i];count[num[i]]++;}for ( int i = 0; i < n; i++ ){if ( count[num[i]] == 1 ){cout << num[i];return(0);}}cout << "None";return(0); }

---

超時解法1：使用LinkedHashMap

提問：java中如何統計數組中出現相同元素的個數？

回答：你可以用map類型，思路大概是這樣的：

• 把數組從第0個開始 保存在<key,value>里
• 作一個對比過程，其中key表示元素，存的過程作一個對比，如果相同，則其相應的value值+1
• 最后輸出key：value

import java.util.Iterator; import java.util.LinkedHashMap; import java.util.Map; import java.util.Map.Entry; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int total = sc.nextInt();// 使用map存儲Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();for (int i = 0; i < total; i++) {int num = sc.nextInt();Integer v = map.get(num);if (v != null) {map.put(num, v + 1);} else {map.put(num, 1);}}// 遍歷mapIterator<?> iter = map.entrySet().iterator();while (iter.hasNext()) {Map.Entry<Integer, Integer> entry = (Entry<Integer, Integer>) iter.next();if ((Integer) entry.getValue() == 1) {System.out.println(entry.getKey());return;}}System.out.println("None");} }

---

超時解法2：同樣的算法，C++不超時

• 讀取數據時，BufferedReader比使用Scanner快一些
• 使用Scanner要花120多ms，BufferedReader大約80ms

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;public class Main {public static void main(String[] args) throws IOException {BufferedReader in = new BufferedReader(new InputStreamReader(System.in));String aa = in.readLine();String[] arr = aa.split(" ");int n = Integer.parseInt(arr[0]);int[] num = new int[100001];int[] count = new int[100001];for (int i = 0; i < n; i++) {num[i] = Integer.parseInt(arr[i + 1]);count[num[i]]++;}for (int i = 0; i < n; i++) {if (count[num[i]] == 1) {System.out.println(num[i]);return;}}System.out.println("None");} }

---

使用Scanner代替BufferedReader：超時更嚴重

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] num = new int[100001];int[] count = new int[100001];for (int i = 0; i < n; i++) {num[i] = sc.nextInt();count[num[i]]++;}for (int i = 0; i < n; i++) {if (count[num[i]] == 1) {System.out.println(num[i]);return;}}System.out.println("None");} }

---

超時解法3：兩層for循環

暴力O(n^2)循環嵌套，耗時也不過如此嘛，雖然超時了，但是居然比Map還快一點點

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int total = sc.nextInt();int[] arr = new int[total];for (int i = 0; i < total; i++) {arr[i] = sc.nextInt();}// 找第一個不重復的int i, j;for (i = 0; i < total; i++) {for (j = 0; j < total; j++) {if(i==j)continue;if (arr[i] == arr[j]) {break;}}if (j == total) {System.out.println(arr[i]);return;}}System.out.println("None");} }

總結

以上是生活随笔為你收集整理的【PAT甲级 LinkedHashMap】1041 Be Unique (20 分) Java、C++版的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。