977_有序数组的平方
/*给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：[-4,-1,0,3,10]
输出：
示例 2：
输入：[-7,-3,2,3,11]
输出：
提示：
1 <= A.length <= 10000
-10000 <= A <= 10000
A 已按非递减顺序排序。
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
* 方案1: 从小往大填(需要找到正负分界点)
*/
int* sortedSquares(int* A, int ASize, int* returnSize)
{
int* ret_val = (int*)malloc(sizeof(int)*ASize);
inti = 0;
inttemp = 0;
inttemp2 = 0;
int* pointer_negative = NULL; /*包括0*/
int* pointer_positive = NULL;
do
{
if(A >= 0)
{
for(i = 0; i < ASize ; i++)
{
temp =A;
ret_val= temp * temp ;
}
break;
}
if(A <= 0)
{
for(i = ASize - 1; i>=0 ; i--)
{
temp = A;
ret_val = temp * temp;
}
break;
}
i = 1;
while(i<ASize)
{
if((A>=0) &&(A <=0))
{
pointer_negative = &A;
pointer_positive = &A ;
break;
}
i++;
}
i = 0;
while((pointer_negative >= &A) || (pointer_positive<=&A))
{
if(pointer_negative < &A)
{
temp = *pointer_positive;
ret_val = temp * temp;
i++;
pointer_positive++;
continue;
}
if(pointer_positive>&A)
{
temp = *pointer_negative;
ret_val = temp * temp;
i++;
pointer_negative--;
continue;
}
temp= *pointer_negative;
temp2 = *pointer_positive ;
temp*= temp;
temp2 *= temp2;
if(temp <= temp2)
{
ret_val = temp;
i++;
pointer_negative--;
}
else
{
ret_val = temp2;
i++;
pointer_positive++;
}
}
break;
}while(0);
*returnSize = ASize;
return ret_val;
}
/*
执行用时 :256 ms, 在所有 C 提交中击败了29.40%的用户
内存消耗 :21.5 MB, 在所有 C 提交中击败了77.71%的用户
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
* 方案2: 从大往小填(利用指针索引)
*/
int* sortedSquares(int* A, int ASize, int* returnSize)
{
int* ret_val = (int*)malloc(sizeof(int)*ASize);
int* head = &A;
int* tail = &A;
inti = ASize-1;
while(i>=0)
{
if(abs(*head)>=abs(*tail))
{
ret_val = (*head)*(*head);
head++;
}
else
{
ret_val = (*tail)*(*tail);
tail--;
}
i--;
}
*returnSize = ASize;
return ret_val;
}
/*
执行用时 :252 ms, 在所有 C 提交中击败了30.71%的用户
内存消耗 :21.4 MB, 在所有 C 提交中击败了80.89%的用户
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
* 方案3: 从大往小填(利用数字索引)
*/
int* sortedSquares(int* A, int ASize, int* returnSize)
{
int* ret_val = (int*)malloc(sizeof(int)*ASize);
inthead = 0;
inttail = ASize-1;
inti = ASize-1;
while(i>=0)
{
if(abs(A)>=abs(A))
{
ret_val = A*A;
head++;
}
else
{
ret_val = A*A;
tail--;
}
i--;
}
*returnSize = ASize;
return ret_val;
}
/*
执行用时 :160 ms, 在所有 C 提交中击败了69.03%的用户
内存消耗 :21.3 MB, 在所有 C 提交中击败了85.35%的用户
*/
惹不起，惹不起，排名前50%我就放过自己了。 从大往小填的头尾指针是从边界开始向中间遍历的，不存在数组越界问题。
页:
[1]