题目
计算两个数组的交
注意事项
每个元素出现次数得和在数组里一样
答案可以以任意顺序给出
样例
nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
解题
参考上道题，这道题只是不需要去重，直接把上道题去重部分程序去除就ok
public class Solution {
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
// Write your code here
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList<Integer> A = new ArrayList<Integer>();
int i=0;
int j=0;
while(i<nums1.length && j<nums2.length ){
if(nums1[i] == nums2[j]){
A.add(nums1[i]);
i++;
j++;
}else if(nums1[i] < nums2[j]){
i++;
}else{
j++;
}
}
int[] res = new int[A.size()];
for( i=0;i<A.size();i++){
res[i] = (int)A.get(i);
}
return res;
}
}
HashMap记录数组1中相同元素出现的次数，数组2找相同，相同次数-1，为0的时候就不是交的部分了
这个HashMap是一个中间存储，方便找到相同元素
public class Solution {
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
// Write your code here
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
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 );
}
}
ArrayList<Integer> A = new ArrayList<Integer>();
for(int i=0;i<nums2.length;i++){
if(map.containsKey(nums2[i])){ // 相同元素
A.add(nums2[i]);
map.put(nums2[i],map.get(nums2[i])- 1 );
if(map.get(nums2[i])==0)
map.remove(nums2[i]); // 去除相同元素
}
}
int[] res = new int[A.size()];
for(int i=0;i<A.size();i++){ // 保存到数组中
res[i] = A.get(i);
}
return res;
}
}
更新
public class Solution {
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
// Write your code here
if(nums1==null || nums2 ==null)
return new int[]{};
HashMap<Integer,int[]> map = new HashMap<Integer,int[]>();
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<nums1.length;i++){
int[] value = map.get(nums1[i]);
if(value == null){
map.put(nums1[i],new int[]{1});
}else{
value[0]++;
}
}
for(int i=0;i<nums2.length;i++){
int[] value = map.get(nums2[i]);
if(value!=null && value[0]>=1){
list.add(nums2[i]);
value[0]--;
}
}
int[] A = new int[list.size()];
for(int i=0;i<list.size();i++){
A[i] = list.get(i);
}
return A;
}
}
自定义value
public class Solution {
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
// Write your code here
if(nums1==null || nums2 ==null)
return new int[]{};
HashMap<Integer,Value> map = new HashMap<Integer,Value>();
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<nums1.length;i++){
Value value = map.get(nums1[i]);
if(value == null){
map.put(nums1[i],new Value(1));
}else{
int v = value.getValue();
value.setValue(v+1);
}
}
for(int i=0;i<nums2.length;i++){
Value value = map.get(nums2[i]);
if(value!=null){
int v = value.getValue();
if(v>=1){
list.add(nums2[i]);
value.setValue(v-1);
}
}
}
int[] A = new int[list.size()];
for(int i=0;i<list.size();i++){
A[i] = list.get(i);
}
return A;
}
public class Value{
int i;
Value(int i){
this.i = i;
}
public void setValue(int i){
this.i = i;
}
public int getValue(){
return i;
}
}
}