c - 使用 C 查找数组中的重复项

Question

我在此链接 https://leetcode.com/problems/contains-duplicate/ 中遇到了问题。有一个整数输入数组。判断是否有重复的整数，否则返回true。

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;

我的结构体的键是两个整数的数组，一个用于标识符，另一个是值数组的索引，这就是 HashMap 的工作原理。

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

然后我们有一个函数来初始化 map ，简单...

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++;
}

将元素放入 map 的函数

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));
}

以及一个在达到限制时调整 map 大小的函数

通过解耦键索引和值数组上的索引，您可以对键进行排序，使您的生活变得更加轻松。 值在数组中的顺序与它们出现的顺序相同，但索引将从 0 到 N 排序。 为此，我将使用一个简单的 selsort 算法，它不是最好的，但却是最简单的......

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() 函数内向 map 添加新条目后立即执行它，它现在仅用于测试。

对索引进行排序后，您可以编写二分搜索算法 eeeasy。现在，如果 map 中已存在 key ，您就可以了。

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];
}

忘了说，通过将键与值解耦，您可以将任何类型用作值，甚至是整个结构......

享受