排序之与零交换

叶茂林

发布于 2023-07-30 13:42:59

2250

题目描述

将 { 0, 1, 2, ..., N-1 } 的任意一个排列进行排序并不困难，这里加一点难度，要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作，将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 }，我们可以通过下列操作完成排序：

Swap(0, 1) ⟹ { 4, 1, 2, 0, 3 }
Swap(0, 3) ⟹ { 4, 1, 2, 3, 0 }
Swap(0, 4) ⟹ { 0, 1, 2, 3, 4 }

本题要求你找出将前 N 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。

输入

输入在第一行给出正整数 N (≤105)；随后一行给出{ 0, 1, 2, ..., N-1 } 的一个排列。数字间以空格分隔。

输出

在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。

输入样例1

10 3 5 7 2 6 4 9 0 8 1

输出样例1

9

思路分析

首先找到0所在位置，然后找该位置应该放的数所在的位置，然后交换这两个位置上的数，有一种情况需要特别判断，当0所在位置为0的位置时，随便找一个位置不正确的数所在位置进行交换。

AC代码

#include<iostream>
using namespace std;
class Solution {
    int n, count = 0, a[256];
public:
    Solution() {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        while(Done()== false){
            int i=Index(0);
            int j=Index(i);
            if(i!=j)
            swap(a[i],a[j]);
            else swap(a[i],a[close()]);
            count++;
        }
        cout<<count;
    }
    int Index(int data) {
        for (int i = 0; i < n; i++)
            if (a[i] == data)
                return i;
    }
    int close(){
        for(int i=0;i<n;i++)
            if(a[i]!=i)
                return i;
    }
    bool Done() {
        for (int i = 0; i < n; i++)
            if (a[i] != i)
                return false;
        return true;
    }
};
int main() {
    Solution test;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-02-08，如有侵权请联系 cloudcommunity@tencent.com 删除

count