app开发哪公司好_字节跳动员工人数多少_网店代运营的套路_新闻头条最新消息今天发布

C语言实现力扣第31题：下一个排列（Next Permutation）

题目描述

题目要求找到一个数组的下一个排列，即字典序中比当前数组更大的下一个排列。如果不存在这样的排列，就将数组重置为最小的排列（即按升序排序）。我们只需在原地对数组进行修改，不能使用额外的空间。

示例

• 输入：{1, 2, 3}
• 输出：{1, 3, 2}

思路分析

1. 从后向前查找第一个下降的元素
   从数组末尾开始，找到第一个比其右侧元素小的元素位置 i。这个元素是需要调整的位置。

2. 从后向前查找第一个比 nums[i] 大的元素
   再次从数组末尾出发，找到第一个比 nums[i] 大的元素，将其位置记为 j。

3. 交换 nums[i] 和 nums[j]
   交换 i 和 j 位置的元素，以保证找到的排列比当前排列更大。

4. 反转 i 后面的元素
   为了得到字典序最小的下一个排列，将 i 后面的元素（降序部分）进行反转，使其变为升序。

通过这四步，我们可以得到所需的下一个排列。

C语言代码实现

#include <stdio.h>// 辅助函数：交换两个整数的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 辅助函数：反转数组指定范围内的元素
void reverse(int* nums, int start, int end) {while (start < end) {swap(&nums[start], &nums[end]);start++;end--;}
}// 实现下一个排列的函数
void nextPermutation(int* nums, int numsSize) {int i = numsSize - 2;// Step 1: 从右到左找到第一个下降的位置while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {// Step 2: 从右到左找到第一个大于 nums[i] 的元素int j = numsSize - 1;while (nums[j] <= nums[i]) {j--;}// Step 3: 交换 nums[i] 和 nums[j]swap(&nums[i], &nums[j]);}// Step 4: 反转 i+1 到末尾的元素reverse(nums, i + 1, numsSize - 1);
}// 主函数：测试用例
int main() {int nums[] = {1, 2, 3};int numsSize = sizeof(nums) / sizeof(nums[0]);nextPermutation(nums, numsSize);printf("Next permutation: ");for (int i = 0; i < numsSize; i++) {printf("%d ", nums[i]);}printf("\n");return 0;
}

代码逐行讲解

辅助函数 swap

void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}

这个函数用于交换两个整数的值。我们在交换 nums[i] 和 nums[j] 时会用到它。

辅助函数 reverse

void reverse(int* nums, int start, int end) {while (start < end) {swap(&nums[start], &nums[end]);start++;end--;}
}

reverse 函数用来反转数组的指定范围，从索引 start 到 end。通过交换两端元素并逐渐向中间靠拢，最终可以将数组局部反转。

主函数 nextPermutation

void nextPermutation(int* nums, int numsSize) {int i = numsSize - 2;// Step 1: 从右到左找到第一个下降的位置while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}

• 我们从数组的倒数第二个元素开始向左遍历，直到找到第一个 nums[i] < nums[i+1] 的位置。这是变化的起点。
• 如果数组已经是降序排列（如 {3, 2, 1}），则 i 会最终为 -1。

    if (i >= 0) {// Step 2: 从右到左找到第一个大于 nums[i] 的元素int j = numsSize - 1;while (nums[j] <= nums[i]) {j--;}// Step 3: 交换 nums[i] 和 nums[j]swap(&nums[i], &nums[j]);}

• 如果 i >= 0，说明我们找到了一个下降点 i，则从数组右侧找到第一个大于 nums[i] 的元素 nums[j]。
• 交换 nums[i] 和 nums[j]，使排列变为比当前排列稍大的状态。

    // Step 4: 反转 i+1 到末尾的元素reverse(nums, i + 1, numsSize - 1);
}

• 最后，我们将 i+1 到末尾的部分反转，使其成为升序，从而达到字典序最小的要求。

主函数 main

int main() {int nums[] = {1, 2, 3};int numsSize = sizeof(nums) / sizeof(nums[0]);nextPermutation(nums, numsSize);printf("Next permutation: ");for (int i = 0; i < numsSize; i++) {printf("%d ", nums[i]);}printf("\n");return 0;
}

• main 函数用于测试。初始化一个数组 nums，调用 nextPermutation 函数后，打印得到的下一个排列。

运行示例

假设输入数组为 {1, 2, 3}，输出如下：

Next permutation: 1 3 2

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，最多进行两次遍历。
• 空间复杂度：O(1)，我们在原地修改数组，不需要额外空间。