美文网首页leedcode
349. Intersection of Two Arrays

349. Intersection of Two Arrays

作者: Mervyn_2014 | 来源:发表于2017-12-01 12:02 被阅读10次

[349. Intersection of Two Arrays] (https://leetcode.com/problems/intersection-of-two-arrays/description/)
给定两个数组,编写一个函数来计算它们的交集。

Example:

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

Note:

每一个元素必须唯一.
结果可以是任意顺序.

class Solution {
   public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();

        Arrays.sort(nums1);
        for (int i = 0; i <nums2.length ; i++) {
            if(binarySearch(nums1,nums2[i])>=0){
                set.add(nums2[i]);
            }
        }
        int[] result = new int[set.size()];
        int k =0;
        for (Integer i : set) {
            result[k++] = i;
        }
        return result;
    }
     public static int binarySearch(int[] nums,int target){
        int low = 0;
        int high = nums.length-1;
        while (low<=high){
            int mid = low+(high-low)/2; //中值不能使用(low+high)/2,因为low+high 可能大于Integer.MAX_VALUE
            if(nums[mid]>target){
                high = mid -1;
            }else if(nums[mid]<target){
                low = mid +1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

相关文章

网友评论

    本文标题:349. Intersection of Two Arrays

    本文链接:https://www.haomeiwen.com/subject/wqnibxtx.html