// 1, 2, 3, 4 | 2, 3, 6, 9
// input [1, 2, 3, 4], [2, 3, 9, 6] output [2, 3]
// input [1, 2, 2, 4], [2, 9] output [2]

// syntax 語法

// characteristic / feature 特徵
// Arrays.sort(num1) -> O(NLogN)
// Set<Integer> -> 2, 3

 public int[] intersection(int[] nums1, int[] nums2) {
     if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
         return new int[]{};
     }
     
     Arrays.sort(nums1); // 1 2 2 4
     // Arrays.sort(nums2); // 2 9
     
     Set<Integer> resultSet = new HashSet<>();
     for (int num2 : nums2) {
         if (binarySearch(nums1, num2)) {
             resultSet.add(num2);
         }
     }
     
     int i = 0;
     int[] result = new int[resultSet.size()];
     for (int num : resultSet) {
         result[i] = num;
         i++;
     }
     
     return result;
 }
 
 public boolean binarySearch(int[] nums, int target) {
     int l = 0;
     int r = nums.length - 1;
     while (l <= r) {
         int mid = (l + r) >>> 1;
         if (nums[mid] == target) {
             return true;
         } else if (nums[mid] > target) {
             r = mid - 1;
         } else {
             l = mid + 1;
         }
     }
     
     return false;
 }

// Input: nums1 = [1,2,2,1], nums2 = [2,2]
// Output: [2,2]

// Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
// Output: [4,9]

// Input: nums1 = [4,9,4,9,5], nums2 = [9,4,9,8,4]
// Output: [4,9,4,9]

public int[] intersect(int[] nums1, int[] nums2) {
   if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
      return new int[]{};
   }
   
   Arrays.asList();
   List<Integer> nums1List = new ArrayList(nums1);
   List<Integer> ansList = new ArrayList();
   
   for (int n2: nums2) {
      if (num1List.contains(n2)) {
         ansList.add(n2);
      }
   }
   
   return ansList.toArray();
}

https://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/#targetText=ArrayList%20has%20O(n)%20time,end%2Fbeginning%20of%20the%20List.

   public int[] intersect(int[] nums1, int[] nums2) {
       if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
           return new int[]{};
      }
   
       List<Integer> nums1List = new ArrayList();
       for (int num1: nums1) {
            nums1List.add(num1);
        }
       List<Integer> ansList = new ArrayList();
   
       for (int n2: nums2) {
         if (nums1List.contains(n2)) {
          ansList.add(n2);
          nums1List.remove(nums1List.indexOf(n2));
         }
      }
   
      int[] ansArray = new int[ansList.size()];
      for (int i = 0; i < ansList.size(); i++) {
         ansArray[i] = ansList.get(i);
      }
    return ansArray;
    }

public class PriorityPool<T> {

    private static final String TAG = PriorityPool.class.getSimpleName();

    private LinkedList<T> mModelList;
    private LinkedList<Integer> mPriorityList;

    private int mLastPeakIndex = -1;

    public PriorityPool() {
        mModelList = new LinkedList<>();
        mPriorityList = new LinkedList<>();
    }

    public synchronized void insert(int priority, T model) {
        if (model == null) {
            Logs.e(TAG, "insert", "model should not be null !!!");
            return;
        }
        mPriorityList.add(priority);
        mModelList.add(model);
    }

    @Nullable
    public synchronized T peak() {
        if (ArrayUtils.isEmpty(mModelList)) {
            Logs.e(TAG, "peak", "mModelList should not be null !!!");
            return null;
        }
        if (ArrayUtils.isEmpty(mPriorityList)) {
            Logs.e(TAG, "peak", "mPriorityList should not be null !!!");
            return null;
        }

        try {
            int max = Collections.max(mPriorityList);
            mLastPeakIndex = mPriorityList.indexOf(max);
            T model = mModelList.get(mLastPeakIndex);

            return model;
        } catch (Exception e) {
            e.printStackTrace();
            Logs.logExceptionToCrashlytics(e);
            return null;
        }
    }

    @Nullable
    public synchronized T poll() {
        if (ArrayUtils.isEmpty(mModelList)) {
            Logs.e(TAG, "poll", "mModelList should not be null !!!");
            return null;
        }
        if (ArrayUtils.isEmpty(mPriorityList)) {
            Logs.e(TAG, "poll", "mPriorityList should not be null !!!");
            return null;
        }

        try {
            int max = Collections.max(mPriorityList);
            int index = mPriorityList.indexOf(max);
            T model = mModelList.get(index);

            mPriorityList.remove(index);
            mModelList.remove(index);

            return model;
        } catch (Exception e) {
            e.printStackTrace();
            Logs.logExceptionToCrashlytics(e);
        }

        return null;
    }

    public synchronized void removeLastPeak() {
        if (ArrayUtils.isEmpty(mModelList)) {
            Logs.e(TAG, "remove", "mModelList should not be null !!!");
            return;
        }
        if (ArrayUtils.isEmpty(mPriorityList)) {
            Logs.e(TAG, "remove", "mPriorityList should not be null !!!");
            return;
        }
        try {
            if (mLastPeakIndex == -1) {
                return;
            }
            mPriorityList.remove(mLastPeakIndex);
            mModelList.remove(mLastPeakIndex);
        } catch (Exception e) {
            e.printStackTrace();
            Logs.logExceptionToCrashlytics(e);
            Logs.e(TAG, "remove", "failure to remove !!!");
        }
    }

    @Nullable
    public T get(int index) {
        if (ArrayUtils.isEmpty(mModelList)) {
            Logs.e(TAG, "get", "mModelList should not be null !!!");
            return null;
        }
        try {
            return mModelList.get(index);
        } catch (Exception e) {
            e.printStackTrace();
            Logs.logExceptionToCrashlytics(e);
            Logs.e(TAG, "get", "failure to get !!!");
        }
        return null;
    }

    public boolean isEmpty() {
        return mModelList == null || mModelList.size() == 0;
    }

    public int size() {
        return mModelList == null ? 0 : mModelList.size();
    }
}