Поиск дубликатов в массиве с помощью C

Question

Я столкнулся с проблемой в этой ссылке https://leetcode.com/problems/contains-duplicate/. Есть входной массив целых чисел.Узнайте, есть ли какие-либо повторяющиеся целые числа, затем верните true, иначе false.

1. Как я могу оптимизировать этот код?

2. Можно ли еще улучшить логику?

В моем коде ниже есть условие if if(hPtr && hPtr->key == *(nums+i)).Я использую элементы массива в качестве ключей.Если так, то каждый ключ не может быть уникальным, если один и тот же элемент повторяется дважды, верно?Поэтому я могу изменить условие if как if(hPtr->key == *(nums + i))?

Если есть какие-либо другие ошибки, пожалуйста, не стесняйтесь указывать.

В C http://troydhanson.github.io/uthash/userguide.html уже есть библиотека хеш-таблици написал код ниже.

struct hash {
        int key;
        int value;
        UT_hash_handle hh;
};

    struct hash *hashtable = NULL;

    void addToHash(int key, int value)
    {
      struct hash *map;
      //I am using the array elements as hash keys
      HASH_FIND_INT(hashtable, &key, map);

      if(map == NULL)
      {
        map = (struct hash*)malloc(sizeof(struct hash));
        map->key = key;
        HASH_ADD_INT(hashtable, key, map);
      }     
      map->value = value;
    }   

    struct hash *findInHash(int key)
    {
        struct hash *h;
        HASH_FIND_INT(hashtable, &key, h);
        return h;
    }

    bool containsDuplicate(int* nums, int numsSize) {
        struct hash *hPtr;
        int target = 0;
        hashtable = NULL;
        if((numsSize <= 1) || (nums == 0)) return false;

        int i, index1 = 0;   

        for(i = 0; i < numsSize; i++)
        {
            /*The below statement will look if the key is already present in 
              the hashtable*/
            hPtr = findInHash(*(nums + i) - target);
            /*If the key is found already, then it look for the value of that 
            key. If the value and the current array element is same, then a 
            duplicate exist*/
            if(hPtr && hPtr->key == *(nums+i))
               return true;
            addToHash(*(nums + i), i);
        }
        struct hash *temp;
        HASH_ITER(hh, hashtable, hPtr, temp) {free(hPtr);}
        return false;
    }

Answer 1

Я думаю, что решение проще, чем вы думаете:

typedef struct {
  int capacity;
  int len;
  int **keys;
  int *values;
} Map;

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

void initMap(Map *map) {
  map -> capacity = 5;
  map -> len = 0;
  map -> keys = malloc(map -> capacity * sizeof(int));
  map -> values = malloc(map -> capacity * sizeof(int));
}

Тогда у нас есть функция для инициализации карты, просто ...

void add(Map *map, int k, int v) {
  if (map -> len == map -> capacity - 1) resize(map);
  map -> values[map -> len] = v;
  map -> keys[map -> len] = malloc(sizeof(int) * 2);
  map -> keys[map -> len][0] = k;
  map -> keys[map -> len][1] = map -> len;
  map -> len++;
}

функция для размещения элементов на карте

void resize(Map *map) {
  map -> capacity *= 2;
  map -> keys = realloc(map -> keys, map -> capacity * sizeof(int) * 2);
  map -> values = realloc(map -> keys, map -> capacity * sizeof(int));
}

и функция изменения размера карты при достижении лимита

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

void sort(Map *map) {
  int i, j;
  int min, tmp;
  for (i = 0; i < map -> len - 1; i++) {
    min = i;
    for (j = i + 1; j < map -> len; j++) {
      if(map -> keys[j][0] < map -> keys[min][0] ) min = j;
    }

    tmp = map -> keys[min][0];
    map -> keys[min][0] = map -> keys[i][0];
    map -> keys[i][0] = tmp;
  }
}

с этим вы закроете свой индекс. Я выполнил бы это сразу после добавления новой записи на карту, внутри функции add (), она сейчас здесь только для тестирования.

Как только ваш индекс отсортирован, вы можете написать алгоритм двоичного поиска, eeeasy. Теперь вы можете это сделать, если ключ уже есть на карте.

int find_recursive(Map *map, int start, int end, int key) {
   if (end >= start) {
        int mid = start + (end - start) / 2;

        if (map -> keys[mid][0] == key)
            return mid;

        if (map -> keys[mid][0] > key)
            return find_recursive(map, start, mid - 1, key);

        return find_recursive(map, mid + 1, end, key);
    }
    return -1;
}

int find(Map *map, int key) {
    return find_recursive(map, 0, map -> len, key);
}

Тааак

  Map map;
  initMap(&map);

  add(&map, 3, 12);
  add(&map, 12, 1);
  add(&map, 1, 2);

  printf("%d %d %d\n",
      map.keys[0][0],
      map.keys[1][0],
      map.keys[2][0]
      );
  // Should print 3 12 1

  sort(&map);

  printf("%d %d %d\n",
      map.keys[0][0],
      map.keys[1][0],
      map.keys[2][0]
      );
  // Should print 1 3 12

  printf("%d\n", find(&map, 12));
  // Should print 2 (the index, 3rd entry)

Сейчас я не могу сделать рабочий пример, я не могу скомпилировать с моей машиной, может быть, позже дома ... извините: (

РЕДАКТИРОВАТЬ: забыл сказать ... чтобы получить значение, которое вы должны сделать map.values[map.keys[find(&map, key)][1]].

Конечно, это должна быть функция:

int get(Map *map, key) {
  int keyindex = find(map, key);
  int valueindex = map -> keys[index][1];
  return map -> values[valueindex];
}

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

наслаждаться