240717.LeetCode——2974.最小数字游戏
题目描述
你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ,同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏,游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下:
每一轮,Alice 先从 nums 中移除一个 最小 元素,然后 Bob 执行同样的操作。
接着,Bob 会将移除的元素添加到数组 arr 中,然后 Alice 也执行同样的操作。
游戏持续进行,直到 nums 变为空。
返回结果数组 arr 。
EX1.
EX2.
提示
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
- nums.length % 2 == 0
代码实现
C语言
暴力解法
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* numberGame(int* nums, int numsSize, int* returnSize)
{int i, j;//定义循环变量int t;//临时交换变量for (i = 0; i < numsSize - 1; i++){for (j = 0; j < numsSize - i - 1; j++){if (nums[j] > nums[j + 1]){t = nums[j];nums[j] = nums[j + 1];nums[j + 1] = t;}}}//进行冒泡排序:对原数组进行从小到大顺序排列for (i = 0; i < numsSize - 1; i = i + 2){t = nums[i];nums[i] = nums[i + 1];nums[i + 1] = t;}//从数组首元素开始进行两两交换*returnSize = numsSize;//注意要返回输出数组的大小return nums;//返回输出数组
}
执行结果
代码思路
根据题目要求,每次取出两个最小的,放入输出数组,但是顺序不规则。所以不妨将其拆分成两次。先进行规则排序再进行两两交换。所以第一个冒泡排序(很久没有用到,所以模板有些生疏),第二个循环,变量隔了一项进行。
暴力解法优化
/*** Note: The returned array must be malloced, assume caller calls free().*//*
自定义比较函数:用于比较两个元素。比较函数应当返回一个整数,表示比较结果:
小于零:表示第一个元素小于第二个元素。
等于零:表示两个元素相等。
大于零:表示第一个元素大于第二个元素。
*/
int compare(const void* a, const void* b)
{return (*(int*)a - *(int*)b);
}int* numberGame(int* nums, int numsSize, int* returnSize)
{int i, j;int t;qsort(nums, numsSize, sizeof(int), compare);//C库函数,<stdlib.h>中for (i = 0; i < numsSize - 1; i = i + 2){t = nums[i];nums[i] = nums[i + 1];nums[i + 1] = t;}*returnSize = numsSize;return nums;
}
执行结果
代码思路
对暴力解法进行优化,将冒泡函数进行封装,使用的是C库自带的函数,但需要自己定义一个比较函数,方法减少了空间复杂度。
其中
qsort()函数
声明
void qsort(void *base, size_t nitems, size_t size, int (*compare)(const void *, const void *));
参数
- base: 指向待排序数组的第一个元素的指针。
- nitems: 数组中的元素数量。
- size: 数组中每个元素的大小(以字节为单位)。
- compare: 比较函数的指针,该函数用于比较两个元素。比较函数应当返回一个整数,表示比较结果。
总结
昨天又没空刷力扣,今天也是终于把江科大51单片机刷完了,也是正式开始学习数据结构与算法了,开始跟夏令营的课程,刷题,今天学的是算法入门和时空复杂度,也学了怎么用MarkDown写文档,现在这篇文档就是用MarkDown编辑器写的,刚好今天周三也是算法日,写到这里已经23.15了哈哈哈哈哈哈哈哈哈哈哈哈,然后的话,就这样吧,保持我的暑期规划不会被破坏,嘿嘿,加油。