LeetCode*350. Intersection of Two Arrays II

1719 단어
LetCode 제목 링크

주의: 영어로 나오는 모든 것은 제목이 제공하는 것으로 답안 코드의 앞줄을 포함합니다.


제목:


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 nums2'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?

  • 해결:


    이 문제의 사상도 앞의 문제를 해결하는 데 쓸 수 있다.먼저 두 개의 수조를 정렬한 다음에 각각 두 개의 하표로 수조를 훑어보고 같은 부분을result수조에 추가하면 된다.앞의 문제를 해결하려면 마지막else 지점에 문장while (i < nums1.length && nums1[i] == nums2[j]) i++;을 추가하십시오

    정답: (Java)

    public class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int[] result = new int[nums2.length];
            int i = 0, j = 0, k = 0;
            while ( i < nums1.length && j < nums2.length) {
                if ( nums1[i] < nums2[j] ) {
                    i++;
                }
                else if ( nums1[i] > nums2[j] ) {
                    j++;
                }
                else {
                    result[k++] = nums1[i++];
                    // add to here
                    j++;
                }
            }
            return Arrays.copyOfRange(result, 0, k);
        }
    }
    

    좋은 웹페이지 즐겨찾기