349/350. Intersection of Two Arrays I/II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.
思路: 由于只输出交集的元素,不要求输出元素的个数,那么用一个hashset来盛放结果元素可以了。
1. 遍历较长的数组,把元素放到用set里面。
2. 遍历较短的数组,判断元素是否存在set里面,如果存在,就说明是交集元素,保存到结果list里面;
3. list转换为array,返回

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> result = new HashSet<Integer>();
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }

        for(int j = 0; j < nums2.length; j++) {
            if (set.contains(nums2[j])) {
                result.add(nums2[j]);
            }
        }

        int[] resultArray = new int[result.size()];
        Iterator<Integer> iter = result.iterator();
        int i = 0;
        while(iter.hasNext()) {
            resultArray[i] = iter.next();
            i++;
        }
        return resultArray;
    }
}

变体: 即输入元素,也输出重复个数的元素. 那么就需要用hashmap来记录元素跟元素的出现次数了。
1. 遍历较长的数组,把元素放到用map里面, element -> count 。
2. 遍历较短的数组,判断元素是否存在map里面,并且count > 0, 如果存在,就说明是交集元素,保存到结果list里面,map中所对应的元素次数-1;
3. list转换为array,返回

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            if (!map.containsKey(nums1[i])) {
                map.put(nums1[i], 1);
            } else {
                int count = map.get(nums1[i]);
                map.put(nums1[i], count + 1);
            }
        }
        for (int j = 0; j < nums2.length; j++) {
            if (map.containsKey(nums2[j]) && map.get(nums2[j]) > 0) {
                list.add(nums2[j]);
                int count = map.get(nums2[j]);
                map.put(nums2[j], count - 1);
            }
        }
        // convert list to array
        int[] res = new int[list.size()];
        for (int k = 0; k < list.size(); k++) {
            res[k] = list.get(k);
        }

        return res;    

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s