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了哈哈哈哈哈哈哈哈哈哈哈哈，然后的话，就这样吧，保持我的暑期规划不会被破坏，嘿嘿，加油。