Advertisement

C算法-线性探测法(某种优化)

阅读量:

leetcode945题,使数组元素互不相同的最小增量操作。
给出一个数组Arr[3,2,1,2,1,7],每次只能对某个元素进行加1操作,最终使得数组中所有元素均不重复。
参考作者题解,其中某些部分似乎与并查集的思路有相似之处。
1、创建一个临时数组tmp,并将其所有元素初始化为-1;
2、当处理到Arr[i]的值为b时,若在tmp数组的对应下标位置尚未存储数据,则直接将其存入,并将该位置的值设置为b+1。这表明若后续仍有相同数值需要放置,应前往b+1的位置尝试寻找空位。
3、若当前tmp[b]的位置已有数据,则需要进一步判断该位置是否可被使用。如果不可用,则继续查看tmp[loc]所指示的位置,并依次更新中间各个tmp[loci]的值以确保路径畅通。

复制代码
    #define MAXLEN 50002
    int minIncrementForUnique(int* A, int ASize) {
    	int i, sum, loc, locstead, b, ltmp;

全部评论 (0)

还没有任何评论哟~