当前位置：首页 > article >正文

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

article 2024/11/5 2:17:13

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

题目描述

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

示例

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

思路分析

从后向前查找第一个下降的元素
从数组末尾开始，找到第一个比其右侧元素小的元素位置 i。这个元素是需要调整的位置。
从后向前查找第一个比 nums[i] 大的元素
再次从数组末尾出发，找到第一个比 nums[i] 大的元素，将其位置记为 j。
交换 nums[i] 和 nums[j]
交换 i 和 j 位置的元素，以保证找到的排列比当前排列更大。
反转 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;
}