[問題] 檢查ArrayList是否重複

看板java作者 (wade)時間8年前 (2016/05/09 13:37), 8年前編輯推噓6(6023)
留言29則, 11人參與, 最新討論串1/2 (看更多)
我有一個簡單的 ArrayList<Integer> a,b及c a = {1,2,3,4,5} b = {2,3,4,5,1} c = {1,2,3,4,5,6} 我想得到a=b , c不等於a與b a與b從排列順序不同但是內容物是相同的 b多出一個6 有沒有什麼一個寫好的方法是能快速的判斷是否相同呢? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.120.251.134 ※ 文章網址: https://www.ptt.cc/bbs/java/M.1462772258.A.B81.html

05/09 13:51, , 1F
參考 Set
05/09 13:51, 1F

05/09 14:00, , 2F
沒有重複的值才能用Set
05/09 14:00, 2F

05/09 14:00, , 3F
有重複的值最簡單就把兩個list都sort後再用equals
05/09 14:00, 3F

05/09 16:14, , 4F
Java沒有內建Multiset,不然這個最適合
05/09 16:14, 4F

05/09 18:56, , 5F
根據數學集合論,可以先判斷length是否相等,不是結案,是的
05/09 18:56, 5F

05/09 18:56, , 6F
話,先針對A每個元素檢查B是否包含,若不成立結案,仍成立就
05/09 18:56, 6F

05/09 18:56, , 7F
再針對B每個元素檢查A是否包含,若仍成立則兩者相等
05/09 18:56, 7F

05/09 18:58, , 8F
不過一樣,如果沒有sort,上面這個方法會是O(N^2),N若真的
05/09 18:58, 8F

05/09 18:58, , 9F
很大,先sort還是會比較快
05/09 18:58, 9F

05/09 18:59, , 10F
^當相等時
05/09 18:59, 10F

05/09 19:00, , 11F
綜合以上,length相等且N很大就先sort用三樓的方法
05/09 19:00, 11F

05/09 20:40, , 12F
{1,2,2,2} {2,1,1,1} 好像也滿足樓上的條件
05/09 20:40, 12F

05/09 20:44, , 13F
樓上對,我搞錯了,要元素無重覆的才能能我滿足我寫的集合
05/09 20:44, 13F

05/09 20:44, , 14F
論定理的前提
05/09 20:44, 14F

05/09 20:44, , 15F
所以還是sort再比是否相等吧
05/09 20:44, 15F

05/09 22:05, , 16F
先轉 array ,再利用 java.util.Arrays, sort 再 equals
05/09 22:05, 16F

05/09 22:57, , 17F
每次看到這類題目就懷念Python
05/09 22:57, 17F

05/09 23:56, , 18F
不用轉array,java.util.Collections有sort
05/09 23:56, 18F

05/09 23:57, , 19F
java8的話List本身就有sort
05/09 23:57, 19F

05/10 00:19, , 20F
哈 原來jdk8已經有了xd
05/10 00:19, 20F

05/10 00:27, , 21F
其實可以自己寫個類似mergeSort的判斷,找ab相同部分
05/10 00:27, 21F

05/10 00:28, , 22F
在找和c不同的部分
05/10 00:28, 22F

05/10 12:12, , 23F
sort後, 把兩個陣列裡面的值變成文字串起來 有沒有equals
05/10 12:12, 23F

05/10 13:33, , 24F
串起來的operation感覺還比逐一相等比較來得多,逐一比較
05/10 13:33, 24F

05/10 13:34, , 25F
遇到不等就結束了,光全部串起來這步驟就不少成本
05/10 13:34, 25F

05/10 14:24, , 26F
串成string只是把int array變成更長的char array...
05/10 14:24, 26F

05/10 17:32, , 27F
{1,11} 跟 {1,1,1} 表示 @w@!
05/10 17:32, 27F

05/17 15:04, , 28F
用hashmap A有的value+1,B有的value-1,最後hashmap有
05/17 15:04, 28F

05/17 15:05, , 29F
value 不為0的元素,則表示不相等
05/17 15:05, 29F
謝謝各位大大 我後來使用Set的方式 參考http://goo.gl/Ssv5Sn ※ 編輯: dwadefans (163.18.42.216), 06/01/2016 14:07:22
文章代碼(AID): #1NC28Yk1 (java)
文章代碼(AID): #1NC28Yk1 (java)