【C语言】有序数组的平方

文章目录 给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

#include<stdio.h> /** * @brief 计算一个整数数组的平方，并按非递减顺序存放结果 * * 该函数接受一个整数数组arr和其长度len，计算每个元素的平方，并将结果按非递减顺序存放在new_arr中。 * 这个函数假设输入数组arr中的元素已经按非递增顺序排列。 * * @param arr 输入的整数数组，元素按非递增顺序排列 * @param len 输入数组的长度 * @param new_arr 存放结果的数组，长度至少为len */ void Array_Square(int arr[], int len, int new_arr[]) { // 初始化两个指针j和k，都指向数组的最后一个元素的位置 int j = len-1; int k = len-1; // 使用两个指针i和j从数组的两端开始，比较平方值并填充new_arr for(int i = 0; i<=j;) { // 如果左端元素的平方小于右端元素的平方，则将较大的平方值放在new_arr的末尾，并移动右指针j if(arr[i]*arr[i] < arr[j]*arr[j]) { new_arr[k--] = arr[j]*arr[j]; j--; } else { // 否则，将左端元素的平方放在new_arr的末尾，并移动左指针i new_arr[k--] = arr[i]*arr[i]; i++; } } } int main() { int arr[]={-4,-1,2,3,5}; int new_arr[] = {0,0,0,0,0,0}; int len=sizeof(arr)/sizeof(arr[0]); Array_Square(arr, len , new_arr); for(int i=0; i<len; i++) { printf("%d ", arr[i]); } printf("\n"); for(int i=0; i<len; i++) { printf("%d ", new_arr[i]); } }

该代码的时间复杂度为O(n)，采用双指针的方式，一个指针指向数组的起始位置，一个指针指向数组的末尾，然后逐一比较。