成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] Intersection of Two Arrays I & II

lucas / 2529人閱讀

Intersection of Two Arrays I Problem

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.

我覺得intersection是最沒有意義的題目,不要求連續(xù),也不是sorted,無趣。

Solution
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Map map = new HashMap();
        List res = new ArrayList();
        for (int i = 0; i < nums1.length; i++) {
            if (!map.containsKey(nums1[i])) map.put(nums1[i], 1);
            else map.put(nums1[i], map.get(nums1[i])+1);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (map.containsKey(nums2[i])) {
                res.add(nums2[i]);
                map.remove(nums2[i]);
            }
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < ans.length; i++) ans[i] = res.get(i);
        return ans;
    }
}
Updated 2018-8 sort two arrays, O(nlogn)
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        Set set = new HashSet<>();
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) i++;
            else if (nums1[i] > nums2[j]) j++;
            else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[set.size()];
        i = 0;
        for (Integer num: set) {
            res[i++] = num;
        }
        return res;
    }
}
two hashsets, O(n)
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set record = new HashSet<>();
        Set intersect = new HashSet<>();
        for (int num: nums1) {
            record.add(num);
        }
        for (int num: nums2) {
            if (record.contains(num)) intersect.add(num);
        }
        int[] res = new int[intersect.size()];
        int i = 0;
        for (Integer num: intersect) {
            res[i++] = num;
        }
        return res;
    }
}
Intersection of Two Arrays II Problem

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

Example

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

Note

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1"s size is small compared to num2"s size? Which algorithm is better?

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
  
If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.
Solution

1. 8ms

import java.util.List;
import java.util.Arrays;

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List res = new ArrayList();
        Map map = new HashMap();
        //Using HashMap to store values in nums1[]
        for (int i = 0; i < nums1.length; i++) {
            if (!map.containsKey(nums1[i])) map.put(nums1[i], 1);
            else map.put(nums1[i], map.get(nums1[i])+1);
        }
        //Modify the map with the amount of equal keys in nums2
        for (int i = 0; i < nums2.length; i++) {
            //Make sure the value of nums2[i] in map is larger than 0
            if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
                res.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i])-1);
            }
        }
        //Transform ArrayList() to int[]
        int[] ans = res.stream().mapToInt(Integer::intValue).toArray();
        return ans;
    }
}

2. 4ms

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int k = 0, l1 = nums1.length, l2 = nums2.length;
        int[] result = new int[l1];
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //After sorted, just so easy
        for (int i = 0, j = 0; i < l1 && j < l2;)
            if (nums1[i] < nums2[j]) i++;
            else if (nums1[i] == nums2[j++]) result[k++] = nums1[i++];
        return Arrays.copyOf(result, k);
    }
}

Update 2018-8 One HashMap, one list convert to array, O(m+n)
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map record = new HashMap<>();
        for (int num: nums1) {
            if (record.containsKey(num)) {
                record.put(num, record.get(num)+1);
            } else record.put(num, 1);
        }
        List res = new ArrayList<>();
        for (int num: nums2) {
            if (record.containsKey(num) && record.get(num) > 0) {
                record.put(num, record.get(num)-1);
                res.add(num);
            }
        }
        int[] intersect = new int[res.size()];
        int i = 0;
        for (int num: res) {
            intersect[i++] = num;
        }
        return intersect;
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/65996.html

相關(guān)文章

  • LeetCode 350. Intersection of Two Arrays II

    摘要:描述給定兩個(gè)數(shù)組,編寫一個(gè)函數(shù)來計(jì)算它們的交集。示例輸入輸出示例輸入輸出說明輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù),應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。我們可以不考慮輸出結(jié)果的順序。思路對(duì)數(shù)組進(jìn)行排序。如果所在的元素大,則向后走一步。 Description Given two arrays, write a function to compute their intersection. Exa...

    余學(xué)文 評(píng)論0 收藏0
  • [LintCode/LeetCode] Intersection of Two Arrays I &

    摘要:先想到的是,其實(shí)也可以,只是需要在遍歷的時(shí)候,添加到數(shù)組中的數(shù)要掉,略微麻煩了一點(diǎn)。在里跑的時(shí)候,也要快一點(diǎn)。另一種類似做法的就快的多了。如果是找出所有包括重復(fù)的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

    enda 評(píng)論0 收藏0
  • 前端 | 每天一個(gè) LeetCode

    摘要:在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目,語言 JavaScript。 在線網(wǎng)站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號(hào): showImg(htt...

    張漢慶 評(píng)論0 收藏0
  • LeetCode 攻略 - 2019 年 7 月下半月匯總(100 題攻略)

    摘要:月下半旬攻略道題,目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題,所以后面會(huì)調(diào)整自己,在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí),攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區(qū)別...

    tain335 評(píng)論0 收藏0
  • leetcode349. Intersection of Two Arrays

    摘要:題目要求找出兩個(gè)無序數(shù)組中重合的值。先將兩個(gè)數(shù)組分別排序,排序完成之后再用兩個(gè)指針分別比較兩個(gè)數(shù)組的值。如果兩個(gè)指針指向的值相同,則向結(jié)果集中添加該元素并且同時(shí)將兩個(gè)指針向前推進(jìn)。答案是為其中一個(gè)數(shù)組通過建立索引的方式排序。 題目要求 Given two arrays, write a function to compute their intersection. Example: ...

    only_do 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

lucas

|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<