Leetcode 350. Intersection of Two Arrays II JAVA語言

1

2

3

4

5

6

<code>Given two arrays, write a function to compute their intersection.</code>

<code>Example:</code>

<code>Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].</code>

<code>Note:</code>

<code>Each element in the result should appear as many times as it shows in both arrays.</code>

<code>The result can be in any order.</code>

題意：求兩個數組的交集，每個元素可以出現多次，傳回的數組順序随意。

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>public</code> <code>int</code><code>[] intersect(</code><code>int</code><code>[] nums1, </code><code>int</code><code>[] nums2) {</code>

<code>        </code><code>List&lt;Integer&gt; list=</code><code>new</code> <code>ArrayList&lt;Integer&gt;();</code>

<code>        </code><code>int</code> <code>length1=nums1.length;</code>

<code>        </code><code>int</code> <code>length2=nums2.length;</code>

<code>        </code><code>int</code><code>[] ret=</code><code>new</code> <code>int</code><code>[Math.min(length1,length2)];</code>

<code>        </code><code>int</code> <code>index=</code><code>0</code><code>;</code>

<code>        </code><code>HashMap&lt;Integer,Integer&gt; map=</code><code>new</code> <code>HashMap&lt;Integer,Integer&gt;();</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;length1;i++){</code>

<code>            </code><code>if</code><code>(!map.containsKey(nums1[i])){</code>

<code>                </code><code>map.put(nums1[i],</code><code>1</code><code>);</code>

<code>            </code><code>}</code><code>else</code><code>{</code>

<code>                </code><code>map.put(nums1[i],map.get(nums1[i])+</code><code>1</code><code>);</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;length2;i++){</code>

<code>            </code><code>if</code><code>(map.containsKey(nums2[i]) &amp;&amp; map.get(nums2[i])!=</code><code>0</code><code>){</code>

<code>                </code><code>map.put(nums2[i],map.get(nums2[i])-</code><code>1</code><code>);</code>

<code>                </code><code>ret[index++]=nums2[i];</code>

<code>        </code><code>return</code> <code>Arrays.copyOfRange(ret,</code><code>0</code><code>,index);</code>

<code>        </code> 

<code>    </code><code>}</code>

<code>}</code>

PS：

1、先申請一個長度是較小長度的數組的數組。

2、用hashmap存放第一個數組的各個數字出現的次數。

3、周遊第二個數組，去hashmap中找，如出現，則hashmap對應的次數減1，同時将key加入到數組中。

4、最後取部分傳回。。。

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1891688