package com.example.demo;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Test350 {

    /**

     * 双指针，先对数据进行排序预处理，然后使用两个指针分别找到两个数组中相同的值，并放到list中

     */

    public int[] intersect(int[] nums1, int[] nums2) {

        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {

            return new int[0];

        }

        List<Integer> list = new ArrayList<>();

        Arrays.sort(nums1);

        Arrays.sort(nums2);

        int pointer1 = 0;

        int pointer2 = 0;

        while (pointer1 < nums1.length && pointer2 < nums2.length) {

            if (nums1[pointer1] < nums2[pointer2]) {

                pointer1++;

            } else if (nums1[pointer1] > nums2[pointer2]) {

                pointer2++;

            } else {

                list.add(nums1[pointer1]);

                pointer1++;

                pointer2++;

            }

        }

        int[] res = new int[list.size()];

        for (int i = 0; i < list.size(); i++) {

            res[i] = list.get(i);

        }

        return res;

    }

    public static void main(String[] args) {

        Test350 t = new Test350();

        int[] arr1 = {4, 9, 5};

        int[] arr2 = {9, 4, 9, 8, 4};

        int[] intersect = t.intersect(arr2, arr1);

        for (int i : intersect) {

            System.out.print(i + " ");

        }

    }

}