Leecode刷题C语言之半有序排列

执行结果:通过

执行用时和内存消耗如下：

 

 

 

代码如下： 

int semiOrderedPermutation(int* nums, int numsSize) {
    int first = 0, last = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 1) {
            first = i;
        }
        if (nums[i] == numsSize) {
            last = i;
        }
    }
    return first + numsSize - 1 - last - (last < first ? 1 : 0);
}

解题思路： 

这段代码的目的是计算一个特定排列（称为半有序排列）的“调整”次数，使其变成完全有序的排列。具体思路如下：

1. 初始化变量：
   • first 用于记录数字 1 在数组中的位置。
   • last 用于记录数组最大值（即 numsSize）在数组中的位置。
2. 遍历数组：
   • 遍历整个数组 nums，大小为 numsSize。
   • 在遍历过程中，更新 first 和 last 的值。当遇到数字 1 时，更新 first 为当前索引 i；当遇到数字等于数组大小 numsSize 时，更新 last 为当前索引 i。
3. 计算调整次数：
   • 为了使数组完全有序，理想情况下 1 应该位于第一个位置，而 numsSize 应该位于最后一个位置。
   • 如果 1 不在第一个位置，我们需要将其移动到第一个位置，这需要 first 次移动（如果 1 已经在第一个位置，则不需要移动）。
   • 如果 numsSize 不在最后一个位置，我们需要将其移动到最后一个位置，这需要 numsSize - 1 - last 次移动（因为从 last 位置到最后一个位置之间有 numsSize - 1 - last 个位置）。
   • 还需要考虑 1 和 numsSize 的相对位置：
     • 如果 last 在 first 的左边（即 last < first），在移动 numsSize 到最后一个位置之后，1 前面会有一个空位，所以移动 1 到第一个位置时，实际上只需要将 1 向右移动 first - 1 次（因为 numsSize 已经占据了最后一个位置，所以不需要额外的一次移动来“腾出”最后一个位置给 numsSize）。但这种情况下，我们之前计算移动 numsSize 时已经考虑了 numsSize - 1 - last 次，所以需要在总数中减去 1 来避免重复计算这次“腾出”位置的移动。
     • 如果 last 在 first 的右边或相同位置，则不需要额外处理，直接按照上述计算即可。
4. 返回结果：
   • 返回 first + numsSize - 1 - last - (last < first ? 1 : 0)，即 1 到第一个位置需要的移动次数加上 numsSize 到最后一个位置需要的移动次数，再根据 1 和 numsSize 的相对位置决定是否减去 1。

综上所述，这段代码通过计算 1 和数组最大值（numsSize）到它们理想位置所需的最少移动次数，来得到使整个数组有序的“调整”次数。

原文地址：https://blog.csdn.net/babyiu5201314/article/details/144412827

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！