摘要:先想到的是,其实也可以,只是需要在遍历的时候,添加到数组中的数要掉,略微麻烦了一点。在里跑的时候,也要快一点。另一种类似做法的就快的多了。如果是找出所有包括重复的截距呢
Problem
Given two arrays, write a function to compute their intersection.
NoticeEach element in the result must be unique.
The result can be in any order.
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
ChallengeCan you implement it in three different algorithms?
Note先想到的是HashSet(),其实HashMap也可以,只是需要在遍历nums2的时候,添加到res数组中的数要remove掉,略微麻烦了一点。在LC里跑的时候,HashSet也要快一点。
另一种类似HashMap做法的BitSet()就快的多了。
public class Solution { public int[] intersection(int[] nums1, int[] nums2) { SetBitSetset1 = new HashSet(); Set set2 = new HashSet(); List ans = new ArrayList(); for (int i = 0; i < nums1.length; i++) set1.add(nums1[i]); for (int i = 0; i < nums2.length; i++) { if (set1.contains(nums2[i])) set2.add(nums2[i]); } int[] res = new int[set2.size()]; int index = 0; for (Integer i: set2) res[index++] = i; return res; } }
public class Solution { public int[] intersection(int[] nums1, int[] nums2) { int[] res = new int[nums1.length]; if (nums1.length == 0 || nums2.length == 0) return new int[0]; int index = 0; BitSet set = new BitSet(); for (int i = 0; i < nums1.length; i++) { set.set(nums1[i]); } for (int i = 0; i < nums2.length; i++) { if (set.get(nums2[i]) == true) { res[index++] = nums2[i]; set.set(nums2[i], false); } } return Arrays.copyOfRange(res, 0, index); } }Follow Up
如果是找出所有包括重复的截距呢?-- Intersection of Two Arrays II
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); int i = 0, j = 0; while (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); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64776.html
Problem Write a program to find the node at which the intersection of two singly linked lists begins. Example The following two linked lists: A: a1 → a2 ↘ ...
摘要:由于要求的时间,所以选择二分法。思路是找到两个数组合并起来的第个元素。这样只需计算两个数组的中位数是第几个元素,代入功能函数即可。据此,根据二分法的性质,我们在递归时可以将前即个元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...
摘要:首先将两个字符串化成字符数组,排序后逐位比较,确定它们等长且具有相同数量的相同字符。然后,从第一个字符开始向后遍历,判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和,分为和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...
摘要:建立一个长度为的数组,统计所有个字符在出现的次数,然后减去这些字符在中出现的次数。否则,循环结束,说明所有字符在和中出现的次数一致,返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....
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 m...
阅读 1756·2023-04-26 02:32
阅读 538·2021-11-18 13:12
阅读 2405·2021-10-20 13:48
阅读 2488·2021-10-14 09:43
阅读 3769·2021-10-11 10:58
阅读 3368·2021-09-30 10:00
阅读 2902·2019-08-30 15:53
阅读 3458·2019-08-30 15:53