350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example: given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

· Each element in the result should appear as many times as it shows in both arrays.

· The result can be in any order.

350. Пересечение двух массивов II

Заданы два массива. Реализуйте функцию, вычисляющую их пересечение.

Например, если nums1 = [1, 2, 2, 1], nums2 = [2, 2], то функция должна вернуть [2, 2].

· Каждый элемент в результирующем массиве должен встречаться столько раз, сколько он встречается в обоих массивах.

· Числа в результирующем массиве могут располагаться в любом порядке

// C++

class Solution {

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

}

};

// Java

public class Solution {

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

}

}

РЕШЕНИЕ

сортировка

Анализ алгоритма

Отсортируем массивы nums1 и nums2. Далее воспользуемся двумя бегущими указателями i и j. Установим их оба на начало массивов: i = j = 0. За линейный проход находим одинаковые элементы в обоих массивах и заносим их в результирующий массив.

Реализация алгоритма

class Solution

{

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2)

{

vector<int> res;

sort(nums1.begin(),nums1.end());

sort(nums2.begin(),nums2.end());

int i = 0, j = 0;

while((i < nums1.size()) && (j < nums2.size()))

if (nums1[i] < nums2[j]) i++;

else

if (nums1[i] > nums2[j]) j++;

else

{

res.push_back(nums1[i]);

i++; j++;

}

return res;

}

};

Java реализация

public class Solution

{

public int[] intersection(int[] nums1, int[] nums2)

{

Arrays.sort(nums1);

Arrays.sort(nums2);

ArrayList<Integer> s = new ArrayList<Integer>();

int i = 0, j = 0;

while((i < nums1.length) && (j < nums2.length))

if (nums1[i] < nums2[j]) i++;

else

if (nums1[i] > nums2[j]) j++;

else

{

s.add(nums1[i]);

i++; j++;

}

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

int k = 0;

for(Integer val : s) res[k++] = val;

return res;

}

}