905_按奇偶排序数组
/*给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
示例：
输入：
输出：
输出 ， 和 也会被接受。
提示：
1 <= A.length <= 5000
0 <= A <= 5000
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortArrayByParity(int* A, int ASize, int* returnSize){
int* ret_val = (int*)calloc(sizeof(int)*ASize);
int* pointer_head = NULL;
int* pointer_tail = NULL;
inti = 0;
if(ret_val==NULL)
{
*returnSize = 0;
return NULL;
}
pointer_head = ret_val;
pointer_tail = &ret_val;
for(i=0;i < ASize ; i ++)
{
if(A % 2 == 0)
{
*pointer_head = A;
pointer_head ++ ;
}
else
{
*pointer_tail = A;
pointer_tail -- ;
}
}
*returnSize = ASize;
return ret_val;
}
/*
方案1:
执行用时 :64 ms, 在所有C提交中击败了25.23%的用户
内存消耗 :10.4 MB, 在所有C提交中击败了77.94%的用户
*/
方法1.遍历原数组，逐一从头尾插入。。。
方法2.可以不遍历，直接从头尾开始判断，遇到不合适的就交换.
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortArrayByParity(int* A, int ASize, int* returnSize){
int* ret_val = (int*)malloc(sizeof(int)*ASize);
int* pointer_head = NULL;
int* pointer_tail = NULL;
inttmp = 0;
memcpy(ret_val,A,sizeof(int)*ASize);
if(ret_val==NULL)
{
*returnSize = 0;
return NULL;
}
pointer_head = ret_val;
pointer_tail = &ret_val;
while(pointer_head < pointer_tail)
{
if((*pointer_head % 2 == 1)&&(*pointer_tail % 2 == 0))
{
tmp = *pointer_tail;
*pointer_tail = *pointer_head;
*pointer_head = tmp;
}
if(*pointer_head % 2 == 0)
{
pointer_head ++;
}
if(*pointer_tail % 2 == 1)
{
pointer_tail --;
}
}
*returnSize = ASize;
return ret_val;
}
/*
方案2:
执行用时 :52 ms, 在所有C提交中击败了30.37%的用户
内存消耗 :10.2 MB, 在所有C提交中击败了84.56%的用户
*/
貌似没有显著的改善.
方法3：使用位运算做奇偶判断，二进制整数的奇偶性完全由第0位确定。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortArrayByParity(int* A, int ASize, int* returnSize)
{
int* ret_val = (int*)malloc(ASize*sizeof(int)) ;
int* pointer_head = NULL;
int* pointer_tail = NULL;
inttmp = 0;
memcpy(ret_val,A,ASize*sizeof(int));
pointer_head = ret_val;
pointer_tail = &ret_val;
while(pointer_head < pointer_tail)
{
if(( ((*pointer_head) & 1) == 1 )
&&( ((*pointer_tail) & 1) == 0)
)
{
tmp = *pointer_tail;
*pointer_tail = *pointer_head;
*pointer_head = tmp;
}
if( ((*pointer_head) & 1) == 0)
{
pointer_head++;
}
if( ((*pointer_tail) & 1) == 1)
{
pointer_tail --;
}
}
*returnSize = ASize;
return ret_val;
}
排名有明显改善.
/*
使用位
执行用时 :40 ms, 在所有C提交中击败了92.52%的用户
内存消耗 :10.2 MB, 在所有C提交中击败了83.82%的用户
*/
风扫地 发表于 2019-6-17 10:38
方法3：使用位运算做奇偶判断，二进制整数的奇偶性完全由第0位确定。
函数的第三个参数，int* returnsize的初始值要怎么给呢 Seawolf 发表于 2019-6-17 14:43
函数的第三个参数，int* returnsize的初始值要怎么给呢
其实就是 ASize啊。
页:
[1]