905_按奇偶排序数组

风扫地

1. /*
   
2. 
   
3. 给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
   
4. 
   
5. 你可以返回满足此条件的任何数组作为答案。
   
6. 
   
7. 
   
8. 
   
9. 示例：
   
10. 
    
11. 输入：[3,1,2,4]
    
12. 输出：[2,4,3,1]
    
13. 输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
    
14. 
    
15. 
    
16. 
    
17. 提示：
    
18. 
    
19.     1 <= A.length <= 5000
    
20.     0 <= A[i] <= 5000
    
21. */
    

复制代码

1. /**
   
2. * Note: The returned array must be malloced, assume caller calls free().
   
3. */
   
4. int* sortArrayByParity(int* A, int ASize, int* returnSize){
   
5.    
   
6.     int* ret_val        = (int*)calloc(sizeof(int)*ASize);
   
7.     int* pointer_head   = NULL;
   
8.     int* pointer_tail   = NULL;
   
9.     int  i              = 0;
   
10.    
    
11.     if(ret_val==NULL)
    
12.     {
    
13.         *returnSize = 0;
    
14.         return NULL;
    
15.     }
    
16.     pointer_head = ret_val;
    
17.     pointer_tail = &ret_val[ASize-1];
    
18. 
    
19.     for(i=0;i < ASize ; i ++)
    
20.     {
    
21.         if(A[i] % 2 == 0)
    
22.         {
    
23.             *pointer_head = A[i];
    
24.             pointer_head ++ ;
    
25.             
    
26.         }
    
27.         else
    
28.         {
    
29.             *pointer_tail = A[i];
    
30.             pointer_tail -- ;
    
31.         }
    
32.     }
    
33.    
    
34.    
    
35.     *returnSize = ASize;
    
36.     return ret_val;
    
37. }
    

复制代码

/*
方案1:
执行用时 :64 ms, 在所有C提交中击败了25.23%的用户
内存消耗 :10.4 MB, 在所有C提交中击败了77.94%的用户
*/

风扫地

方法1.遍历原数组，逐一从头尾插入。。。


方法2.可以不遍历，直接从头尾开始判断，遇到不合适的就交换.

1. /**
   
2. * Note: The returned array must be malloced, assume caller calls free().
   
3. */
   
4. int* sortArrayByParity(int* A, int ASize, int* returnSize){
   
5.    
   
6.     int* ret_val        = (int*)malloc(sizeof(int)*ASize);
   
7.     int* pointer_head   = NULL;
   
8.     int* pointer_tail   = NULL;
   
9.     int  tmp            = 0;
   
10.    
    
11.     memcpy(ret_val,A,sizeof(int)*ASize);
    
12.     if(ret_val==NULL)
    
13.     {
    
14.         *returnSize = 0;
    
15.         return NULL;
    
16.     }
    
17.    
    
18.     pointer_head = ret_val;
    
19.     pointer_tail = &ret_val[ASize-1];
    
20.     while(pointer_head < pointer_tail)
    
21.     {
    
22.         if((*pointer_head % 2 == 1)&&(*pointer_tail % 2 == 0))
    
23.         {
    
24.             tmp           = *pointer_tail;
    
25.             *pointer_tail = *pointer_head;
    
26.             *pointer_head = tmp;
    
27.         }
    
28.         
    
29.         if(*pointer_head % 2 == 0)
    
30.         {
    
31.             pointer_head ++;
    
32.         }
    
33.         
    
34.         if(*pointer_tail % 2 == 1)
    
35.         {
    
36.             pointer_tail --;
    
37.         }   
    
38.     }
    
39.    
    
40.     *returnSize = ASize;
    
41.     return ret_val;
    
42. }
    

复制代码

1. /*
   
2. 方案2:
   
3. 执行用时 :52 ms, 在所有C提交中击败了30.37%的用户
   
4. 内存消耗 :10.2 MB, 在所有C提交中击败了84.56%的用户
   
5. */

复制代码

貌似没有显著的改善.

风扫地

方法3：使用位运算做奇偶判断，二进制整数的奇偶性完全由第0位确定。

1. /**
   
2. * Note: The returned array must be malloced, assume caller calls free().
   
3. */
   
4. int* sortArrayByParity(int* A, int ASize, int* returnSize)
   
5. {
   
6.    
   
7.     int* ret_val        = (int*)malloc(ASize*sizeof(int)) ;
   
8.     int* pointer_head   = NULL;
   
9.     int* pointer_tail   = NULL;
   
10.     int  tmp            = 0;
    
11.    
    
12.     memcpy(ret_val,A,ASize*sizeof(int));
    
13.    
    
14.    
    
15.     pointer_head = ret_val;
    
16.     pointer_tail = &ret_val[ASize-1];
    
17.     while(pointer_head < pointer_tail)
    
18.     {
    
19.         if(  ( ((*pointer_head) & 1) == 1 )
    
20.            &&( ((*pointer_tail) & 1) == 0  )
    
21.         )
    
22.         {
    
23.             tmp           = *pointer_tail;
    
24.             *pointer_tail = *pointer_head;
    
25.             *pointer_head = tmp;
    
26.         }
    
27.         
    
28.         if( ((*pointer_head) & 1) == 0)
    
29.         {
    
30.             pointer_head++;
    
31.         }
    
32.         
    
33.         if( ((*pointer_tail) & 1) == 1)
    
34.         {
    
35.             pointer_tail --;
    
36.         }   
    
37.     }
    
38.     *returnSize = ASize;
    
39.     return ret_val;
    
40. }

复制代码

排名有明显改善.

1. /*
   
2. 使用位
   
3. 执行用时 :40 ms, 在所有C提交中击败了92.52%的用户
   
4. 内存消耗 :10.2 MB, 在所有C提交中击败了83.82%的用户
   
5. */

复制代码

Seawolf

风扫地 发表于 2019-6-17 10:38
方法3：使用位运算做奇偶判断，二进制整数的奇偶性完全由第0位确定。

函数的第三个参数，int* returnsize的初始值要怎么给呢

风扫地

Seawolf 发表于 2019-6-17 14:43
函数的第三个参数，int* returnsize的初始值要怎么给呢

其实就是 ASize啊。