349. Intersection of Two Arrays

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

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

· Each element in the result must be unique.

· The result can be in any order.

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

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

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

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

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

// C++

class Solution {

public:

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

}

};

// Java

public class Solution {

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

}

}

РЕШЕНИЕ

сортировка

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

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

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

class Solution

{

public:

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

{

set<int> s;

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

{

s.insert(nums1[i]);

i++; j++;

}

vector<int> res(s.begin(),s.end());

return res;

}

};

Java реализация

public class Solution

{

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

{

Arrays.sort(nums1);

Arrays.sort(nums2);

HashSet<Integer> s = new HashSet<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;

}

}

Java реализация – использование retainAll

class Solution

{

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

{

HashSet<Integer> s1 = new HashSet<Integer>();

for(int val : nums1) s1.add(val);

HashSet<Integer> s2 = new HashSet<Integer>();

for(int val : nums2) s2.add(val);

// в s1 остаются только те элементы, которые присутствуют в s2

s1.retainAll(s2);

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

int ind = 0 ;

for(int val : s1) res[ind++] = val;

return res;

}

}