山西省网站建设备案表,成都专业网站建设,本地建站软件有哪些,ftp上传网站步骤文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
排序
二【题目难度】
中等
三【题目编号】
面试题10.11.峰与谷
四【题目描述】
在一个整数… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
排序
二【题目难度】
中等
三【题目编号】
面试题10.11.峰与谷
四【题目描述】
在一个整数数组中“峰”是大于或等于相邻整数的元素相应地“谷”是小于或等于相邻整数的元素。例如在数组{5, 8, 4, 2, 3, 4, 6}中{8, 6}是峰 {5, 2}是谷。现在给定一个整数数组将该数组按峰与谷的交替顺序排序。
五【题目示例】
示例: 输入: [5, 3, 1, 2, 3]输出: [5, 1, 3, 2, 3]
六【题目提示】 n u m s . l e n g t h 10000 nums.length 10000 nums.length10000
七【解题思路】
首先对数组从小到大排序排序之后我们仔细思考题目的要求题目要求数组按照“大-小”的顺序对数组重新组合现在对于排序后的任意一个位置i的数字来说i-1位置的数字小于位置i的数组位置i1的数字大于位置i的数字而位置i1的数字又大于位置i-1和位置i的数字所以我们只需要将位置i的数字和位置i1的数字进行交换这样位置i的数字就大于位置i1的数字了而且位置i的数字也大于位置i-1的数字就形成了“峰”和“谷”只需要每两个数字为一组遍历数组即可本题不需要返回值
八【时间频度】
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) n n n为传入的数组的长度空间复杂度 O ( l o g n ) O(logn) O(logn) n n n为传入的数组的长度
九【代码实现】
Java语言版
class Solution {public void wiggleSort(int[] nums) {Arrays.sort(nums);for(int i 0;i nums.length - 1;i2){int temp nums[i];nums[i] nums[i 1];nums[i 1] temp;}}
}C语言版
int compare(const void *a, const void *b)
{return *(int *)a - *(int *)b;
}void wiggleSort(int* nums, int numsSize)
{qsort(nums, numsSize, sizeof(int), compare);for(int i 0;i numsSize - 1;i 2){int temp nums[i];nums[i] nums[i 1];nums[i 1] temp;}
}Python语言版
class Solution:def wiggleSort(self, nums: List[int]) - None:nums.sort()for i in range(0, len(nums) - 1, 2):temp nums[i]nums[i] nums[i 1]nums[i 1] tempC语言版
class Solution {
public:void wiggleSort(vectorint nums) {if(nums.size() 0){return;}sort(nums.begin(), nums.end());for(int i 0;i nums.size() - 1;i 2){int temp nums[i];nums[i] nums[i 1];nums[i 1] temp;}}
};十【提交结果】 Java语言版 C语言版 Python语言版 C语言版
