leecode每日刷題1
題目描述
示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，陣列變為 [16,1,0,9,100]
排序后，陣列變為 [0,1,9,16,100]
示例 2：
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非遞減順序 排序
進階：
請你設計時間復雜度為 O(n) 的演算法解決本問題
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題程序
- 方法1
①先將陣列內的數平方
②使用快排進行排序
③時間復雜度為O(nlogn)
解題代碼//值的交換 void swap(int *a, int *b){ int tmp; tmp = *a; *a = *b; *b = tmp; } //先寫一個快速排序 void quickSort(int *nums, int numsSize ,int begin, int end){ int i, j; if( begin < end){ i = begin + 1; j = end; while(i < j){ if(nums[i] > nums[begin]){ swap(&nums[i], &nums[j]); j--; }else{ i++; } } if(nums[i]>=nums[begin]){ i--; } swap(&nums[begin],&nums[i]); quickSort(nums,numsSize,begin,i); quickSort(nums,numsSize,j,end); } } int* sortedSquares(int* nums, int numsSize, int* returnSize){ for(int i = 0; i < numsSize; i++){ nums[i]= nums[i]*nums[i]; } quickSort(nums, numsSize, 0, numsSize-1); *returnSize = numsSize; return nums; } - 方法2
根據原陣列就是一個倒序排列的陣列，可知，在正數和負數分界處，左邊負數的絕對值為從大到小排列，而右邊的數為從小到大，故可設定一個新陣列，通過比較兩個邊界的最大值，確定新陣列的最大值，往下類推
①定義兩個數字指標left與right，left指向原陣列的最左邊下標，right指向最右邊的下標原陣列:-4, -1, 0, 3, 10 絕對值后的陣列: 4, 1, 0, 3, 10 平方后的陣列: 16, 1, 0, 3, 100 第一次: left right 因為16<100 故新陣列newNums[4] = 100 right往左移 平方后的陣列: 16, 1, 0, 3, 100 第一次: left right 繼續16和3比較，挑出最大值 ......
②比較陣列在left和right下標對應的值的平方，大的值，存入新陣列中，若left值的大，則left需往右移，同理,right需往左移
③回圈②直至新陣列賦值完畢
解題代碼int Sqrt(int num){ return num*num; } //不使用排序 利用雙指標實作 int* sortedSquares(int* nums, int numsSize, int* returnSize){ int left = 0, right = numsSize - 1; int *returnNums = (int *)malloc(sizeof(int)*numsSize); //定義一個回傳陣列，并賦予地址 int index = numsSize - 1; while(index>=0){ if(Sqrt(nums[left]) > Sqrt(nums[right])){ returnNums[index] = Sqrt(nums[left]); left++; } else{ returnNums[index] = Sqrt(nums[right]); right--; } index--; } *returnSize = numsSize; return returnNums; }
題目描述
給你一個陣列，將陣列中的元素向右輪轉 k 個位置，其中 k 是非負數，
示例 1:
輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋:
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotate-array
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
實作代碼
- 方法一
兩種實作方式：void rotate(int* nums, int numsSize, int k){ k=k%numsSize; int tmpNums[numsSize]; for(int i = 0; i < numsSize; i++){ tmpNums[i] = nums[(numsSize-k+i)%numsSize]; } for(int i=0;i<numsSize;i++){ nums[i]=tmpNums[i]; } }void rotate(int* nums, int numsSize, int k){ k = k % numsSize; if(k == 0){ return; } int *tmpNums = malloc(sizeof(int)*k); for(int i = 0; i < k; i++){ tmpNums[i] = nums[numsSize-i-1]; } for(int j = numsSize-1; j >= 0; j--){ if(j >= k){ nums[j] = nums[j -k]; } else{ nums[j] = tmpNums[k -j-1]; } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/433293.html
標籤：其他