資訊專欄INFORMATION COLUMN
摘要：先想到的是，其實(shí)也可以，只是需要在遍歷的時(shí)候，添加到數(shù)組中的數(shù)要掉，略微麻煩了一點(diǎn)。在里跑的時(shí)候，也要快一點(diǎn)。另一種類似做法的就快的多了。如果是找出所有包括重復(fù)的截距呢
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()，其實(shí)HashMap也可以，只是需要在遍歷nums2的時(shí)候，添加到res數(shù)組中的數(shù)要remove掉，略微麻煩了一點(diǎn)。在LC里跑的時(shí)候，HashSet也要快一點(diǎn)。
另一種類似HashMap做法的BitSet()就快的多了。
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set set1 = 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;
}
}
BitSet
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
如果是找出所有包括重復(fù)的截距呢？-- 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);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.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 ↘ ...
摘要：由于要求的時(shí)間，所以選擇二分法。思路是找到兩個(gè)數(shù)組合并起來(lái)的第個(gè)元素。這樣只需計(jì)算兩個(gè)數(shù)組的中位數(shù)是第幾個(gè)元素，代入功能函數(shù)即可。據(jù)此，根據(jù)二分法的性質(zhì)，我們?cè)谶f歸時(shí)可以將前即個(gè)元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...
摘要：首先將兩個(gè)字符串化成字符數(shù)組，排序后逐位比較，確定它們等長(zhǎng)且具有相同數(shù)量的相同字符。然后，從第一個(gè)字符開(kāi)始向后遍歷，判斷和中以這個(gè)坐標(biāo)為中點(diǎn)的左右兩個(gè)子字符串是否滿足第一步中互為的條件設(shè)分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...
摘要：建立一個(gè)長(zhǎng)度為的數(shù)組，統(tǒng)計(jì)所有個(gè)字符在出現(xiàn)的次數(shù)，然后減去這些字符在中出現(xiàn)的次數(shù)。否則，循環(huán)結(jié)束，說(shuō)明所有字符在和中出現(xiàn)的次數(shù)一致，返回。 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...
閱讀 1872·2023-04-26 02:32
閱讀 601·2021-11-18 13:12
閱讀 2480·2021-10-20 13:48
閱讀 2559·2021-10-14 09:43
閱讀 3870·2021-10-11 10:58
閱讀 3595·2021-09-30 10:00
閱讀 2970·2019-08-30 15:53
閱讀 3517·2019-08-30 15:53
