Минимизация временной сложности при зацикливании двух массивов

Question

Для вводного курса по информатике мы должны написать функцию, которая находит пересечение двух массивов, каждый из которых отображается только один раз и не выделяет больше места, чем нам нужно.

Например:

массив A = {1, 2, 3, 3, 3, 5}

массив B = {2, 2, 2, 3, 5, 6}

пересечение A и B = {2, 3, 5}

Как я могу выполнить sh, не зацикливаясь на обоих массивах дважды? В моем нынешнем виде у меня есть:

//find how large of an array I'll need
for array A 
  for array A
    if A[i] is already somewhere earlier in array A
      stop
    else 
      loop through array B 
      if A[i] is in array B, increment a counter


declare a new array of size counter  

//add unique elements to the array
for array A 
  for array A
    if A[i] is already somewhere earlier in array A
      stop
    else 
      loop through array B 
      if A[i] is in array B, add it to the new array

Кажется, что это будет действительно неэффективно, у меня есть два почти идентичных вложенных цикла for. Если бы я использовал python, я мог бы просто добавить уникальные элементы в список, но есть ли способ сделать что-то подобное в C? Я мог бы просто объявить массив максимально необходимого размера, но я пытаюсь минимизировать сложность пространства.

Answer 1

Если вы знаете о наборах, вы можете использовать это. Сложность времени будет O(n)

. Вы можете узнать больше о наборе и как его реализовать в C здесь .

Тогда вы можете сделать что-то вроде это (записано Java):

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = getSet(nums1);
    Set<Integer> set2 = getSet(nums2);

    Set<Integer> ans = new HashSet<>();

    for(Integer i: set1) {
        if(set2.contains(i)) {
            ans.add(i);
        }
    }

    int[] ret = new int[ans.size()];

    int count = 0;
    for(Integer i: ans) {
        ret[count] = i;
        count++;
    }

    return ret;
}

public Set<Integer> getSet(int[] arr) {
    Set<Integer> set = new HashSet<>();

    for(int a: arr) { set.add(a); }
    return set;
}