建信金科笔试第一题复盘，从O(N2）到O（N）

因算法复杂度过高失败告终

int* a(int* arr, int arrLen) { // write code here int count[100000]; int* res[arrLen+1]; for(int i=0;i<arrLen;i++){ count[arr[i]]++; } for(int i=0;i<arrLen;i++){ if(count[arr[i]]!=2){ *res[i]=-1; }else{ for(int j=i+1;j<arrLen;j++){ if(arr[j]==arr[i]){ *res[i]=j+1; *res[j]=i+1; } } } } return *res; }

修改，通过引入存储第一次下标的数组，防止o（N2），还有计数引入到便利数组中一起

#include <stdlib.h>

#include <string.h>

#define MAX_VAL 100000 //

假设数组中的元素值在 0 到 99999 范围内

int* a(int* arr, int arrLen) { int* res = (int*)malloc(arrLen * sizeof(int)); for (int i = 0; i < arrLen; ++i) { res[i] = -1; // 默认初始化为 -1 }

// 计数数组，统计每个元素出现的次数

int* count = (int*)calloc(MAX_VAL + 1, sizeof(int)); // 存储每个元素的第一次出现位置

int* pos = (int*)malloc((MAX_VAL + 1) * sizeof(int)); for (int i = 0; i <= MAX_VAL; ++i) { pos[i] = -1; }

// 遍历输入数组，记录出现次数和位置

for (int i = 0; i < arrLen; ++i) { int value = arr[i]; count[value]++;

if (count[value] == 1) { pos[value] = i; // 第一次出现，记录位置 } else if (count[value] == 2) { // 第二次出现时，设置配对索引int firstIndex = pos[value]; res[firstIndex] = i + 1; res[i] = firstIndex + 1; } }

// 释放内存

free(count); free(pos);

return res; }

各位佬，如果是存c，不像c++那样引入哈希表的话，还有更好的方法吗