对一系列数字进行排序-就地

我正在尝试解决以下问题:

我们得到一个包含“n”个对象的数组。每个对象在创建时都会根据其创建顺序分配一个从 1 到“n”的唯一编号。这意味着序列号为“3”的对象是在序列号为“4”的对象之前创建的。

编写一个函数,以 O(n)O(n) 中的创建序列号对对象进行就地排序,并且没有任何额外的空间。为简单起见,我们假设我们传递了一个仅包含序列号的整数数组,尽管每个数字实际上都是一个对象。

例如:输入:[2, 6, 4, 3, 1, 5] 输出:[1, 2, 3, 4, 5, 6]

我的方法:

void sortInPlace(int *arr,int n){

    for(int i=0;i<n;i++){

        if(arr[i] != arr[arr[i]-1]){
            swap(arr[i],arr[arr[i]-1]);
        }
    }


}

int main(){

    int n;
    cout<<"n Enter number of elements:";
    cin>>n;

    int arr[n];
    cout<<"n Enter the elements :";
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    sortInPlace(arr,n);

    cout<<"n Sorted Array :";
    for(int i = 0; i < n ; i++){

        cout<<arr[i];
    }

}


但是,这不会产生正确的结果。

实际解决方案:

我能找到的唯一区别是他们使用的 While 循环。

解决方案中的 while 循环有一个额外的迭代来增加 'i' ,而 , 我的解决方案在 for 循环中执行它而不需要额外的迭代。

示例:我的方法


Input : [1,5,6,4,3,2]
Output : [1,3,2,4,5,6]
Expected output : [1,2,3,4,5,6]

但是,为什么它不起作用?有人可以告诉我我是否遗漏了什么吗?

回答

在 的每次迭代中for (int i=0; i < n; i++)i都会递增。

如果没有进行交换,while循环只会增加i

为了获得相同的行为,进行交换时for版本不得增加i


以上是对一系列数字进行排序-就地的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>