建信金科笔试第一题复盘,从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++那样引入哈希表的话,还有更好的方法吗