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

#建信金科校招#
全部评论
C看得人头皮发麻
点赞 回复 分享
发布于 11-10 22:24 上海
不用哈希表的话,最简单可以用个n*2的二维数组,分别存值对应的俩下标。再用个flag数组标记是否刚好是两个下标
点赞 回复 分享
发布于 11-11 01:32 广东
你用C的话,数组就是哈希表啊。位置当成索引,用两个数组分别存出现次数和下标就好了
点赞 回复 分享
发布于 11-11 10:19 四川
头皮发麻,写的时候感觉还行,不难
点赞 回复 分享
发布于 11-21 17:17 福建

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务