977_有序数组的平方

风扫地

1. /*
   
2. 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
   
3. 
   
4. 示例 1：
   
5. 
   
6. 输入：[-4,-1,0,3,10]
   
7. 输出：[0,1,9,16,100]
   
8. 
   
9. 示例 2：
   
10. 
    
11. 输入：[-7,-3,2,3,11]
    
12. 输出：[4,9,9,49,121]
    
13. 
    
14. 提示：
    
15.     1 <= A.length <= 10000
    
16.     -10000 <= A[i] <= 10000
    
17.     A 已按非递减顺序排序。
    
18. */
    

复制代码

1. /**
   
2. * Note: The returned array must be malloced, assume caller calls free().
   
3. * 方案1: 从小往大填(需要找到正负分界点)
   
4. */
   
5. int* sortedSquares(int* A, int ASize, int* returnSize)
   
6. {
   
7.     int* ret_val            = (int*)malloc(sizeof(int)*ASize);
   
8.     int  i                  = 0;
   
9.     int  temp               = 0;
   
10.     int  temp2              = 0;
    
11.     int* pointer_negative   = NULL; /*包括0*/
    
12.     int* pointer_positive   = NULL;
    
13.    
    
14.     do
    
15.     {
    
16.         if(A[0] >= 0)
    
17.         {
    
18.             for(i = 0; i < ASize ; i++)
    
19.             {
    
20.                 temp =A[i];
    
21.                 ret_val[i]  = temp * temp   ;
    
22.             }
    
23.             break;
    
24.         }
    
25.         
    
26.         if(A[ASize-1] <= 0)
    
27.         {
    
28.             for(i = ASize - 1; i>=0 ; i--)
    
29.             {
    
30.                 temp = A[i];
    
31.                 ret_val[ASize - 1-i] = temp * temp;
    
32.             }            
    
33.             break;
    
34.         }
    
35.         
    
36.         i = 1;
    
37.         while(i<ASize)
    
38.         {
    
39.             if((A[i]>=0) &&(A[i-1] <=0))
    
40.             {
    
41.                 pointer_negative = &A[i-1]  ;
    
42.                 pointer_positive = &A[i]    ;
    
43.                 break;
    
44.             }
    
45.             i++;
    
46.         }
    
47.         
    
48.         i = 0;
    
49.         while((pointer_negative >= &A[0]) || (pointer_positive<=&A[ASize-1]))
    
50.         {
    
51.             if(pointer_negative < &A[0])
    
52.             {
    
53.                 temp = *pointer_positive;
    
54.                 ret_val[i] = temp * temp;
    
55.                 i++;
    
56.                 pointer_positive++;
    
57.                 continue;
    
58.             }
    
59.             
    
60.             if(pointer_positive>&A[ASize-1])
    
61.             {
    
62.                 temp = *pointer_negative;
    
63.                 ret_val[i] = temp * temp;
    
64.                 i++;
    
65.                 pointer_negative--;
    
66.                 continue;
    
67.             }
    
68.             
    
69.             
    
70.             temp  = *pointer_negative;
    
71.             temp2 = *pointer_positive ;
    
72.             
    
73.             temp  *= temp;
    
74.             temp2 *= temp2;
    
75.             
    
76.             if(temp <= temp2)
    
77.             {
    
78.                 ret_val[i] = temp;
    
79.                 i++;
    
80.                 pointer_negative--;
    
81.             }
    
82.             else
    
83.             {
    
84.                 ret_val[i] = temp2;
    
85.                 i++;
    
86.                 pointer_positive++;
    
87.             }
    
88.         }
    
89.         
    
90.         break;
    
91.         
    
92.         
    
93.         
    
94.     }while(0);
    
95.    
    
96.     *returnSize = ASize;
    
97.     return ret_val;
    
98. }
    
99. /*
    
100. 执行用时 :256 ms, 在所有 C 提交中击败了29.40%的用户
     
101. 内存消耗 :21.5 MB, 在所有 C 提交中击败了77.71%的用户
     
102. */
     

复制代码

风扫地

1. /**
   
2. * Note: The returned array must be malloced, assume caller calls free().
   
3. * 方案2: 从大往小填(利用指针索引)
   
4. */
   
5. int* sortedSquares(int* A, int ASize, int* returnSize)
   
6. {
   
7.     int* ret_val = (int*)malloc(sizeof(int)*ASize);
   
8.     int* head    = &A[0];
   
9.     int* tail    = &A[ASize-1];
   
10.     int  i       = ASize-1;
    
11.    
    
12.     while(i>=0)
    
13.     {
    
14.         if(abs(*head)>=abs(*tail))
    
15.         {
    
16.             ret_val[i] = (*head)*(*head);
    
17.             head++;
    
18.         }
    
19.         else
    
20.         {
    
21.             ret_val[i] = (*tail)*(*tail);
    
22.             tail--;
    
23.         }
    
24.         i--;
    
25.     }
    
26.     *returnSize = ASize;
    
27.     return ret_val;
    
28. }
    
29. 
    
30. /*
    
31. 执行用时 :252 ms, 在所有 C 提交中击败了30.71%的用户
    
32. 内存消耗 :21.4 MB, 在所有 C 提交中击败了80.89%的用户
    
33. */
    

复制代码

风扫地

1. /**
   
2. * Note: The returned array must be malloced, assume caller calls free().
   
3. * 方案3: 从大往小填(利用数字索引)
   
4. */
   
5. int* sortedSquares(int* A, int ASize, int* returnSize)
   
6. {
   
7.     int* ret_val = (int*)malloc(sizeof(int)*ASize);
   
8.     int  head    = 0;
   
9.     int  tail    = ASize-1;
   
10.     int  i       = ASize-1;
    
11.    
    
12.     while(i>=0)
    
13.     {
    
14.         if(abs(A[head])>=abs(A[tail]))
    
15.         {
    
16.             ret_val[i] = A[head]*A[head];
    
17.             head++;
    
18.         }
    
19.         else
    
20.         {
    
21.             ret_val[i] = A[tail]*A[tail];
    
22.             tail--;
    
23.         }
    
24.         i--;
    
25.     }
    
26.     *returnSize = ASize;
    
27.     return ret_val;   
    
28. }
    
29. 
    
30. /*
    
31. 执行用时 :160 ms, 在所有 C 提交中击败了69.03%的用户
    
32. 内存消耗 :21.3 MB, 在所有 C 提交中击败了85.35%的用户
    
33. */
    

复制代码

惹不起，惹不起，排名前50%我就放过自己了。

风扫地

从大往小填的头尾指针是从边界开始向中间遍历的，不存在数组越界问题。