C语言实现基数排序二分查找
基数排序二分查找
#define MAX_N 65536
#define MAX_M 32768
#define forLoop(i,begin,end)for(int i = begin;
i < end;
i++)
#define _forLoop(i,begin,end)for(int i = begin;
i > end;
i--)
#define L(x) (x & 0xffff)
#define H(x) ((x>>16)&0xffff)
void radix_sort(int *arr,int *main_ind,int n){
int cnt[MAX_N] = {0};
int *temp = (int *)malloc(sizeof(int)*n);
int *ind = (int *)malloc(sizeof(int)*n);
forLoop(i,0,n)cnt[L(arr[i])]+=1;
forLoop(i,1,MAX_N)cnt[i] += cnt[i-1];
_forLoop(i,n-1,-1){
temp[--cnt[L(arr[i])]] = arr[i];
ind[cnt[L(arr[i])]] = i;
}
memset(cnt,0,sizeof(cnt));
forLoop(i,0,n)cnt[H(temp[i])] += 1;
forLoop(i,MAX_M,MAX_N+MAX_M)cnt[i%MAX_N] += cnt[(i-1)%MAX_N];
_forLoop(i,n-1,-1){
arr[--cnt[H(temp[i])]] = temp[i];
main_ind[cnt[H(temp[i])]] = ind[i];
}
free(temp);
free(ind);
return;
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int *ind = (int*)malloc(sizeof(int)*numsSize);
radix_sort(nums,ind,numsSize);
int i = 0,j = numsSize-1;
int *ret = (int*)malloc(sizeof(int)*2);
int temp;
while(i < j){
temp = nums[i] + nums[j];
if(temp == target){
ret[0] = ind[i];
ret[1] = ind[j];
break;
}
if(temp < target)i++;
else j--;
}
returnSize[0] = 2;
return ret;
}
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 孩子不是实现父母欲望的工具——林哈夫
- 一起来学习C语言的字符串转换函数
- C语言字符函数中的isalnum()和iscntrl()你都知道吗
- opencv|opencv C++模板匹配的简单实现
- C语言浮点函数中的modf和fmod详解
- Node.js中readline模块实现终端输入