数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究排序数组，忽略子数组中的元素
本文介绍了如何忽略同一数组中存在的子数组元素来排序数组。我们将讨论两种方法。第一种方法是蛮力法，时间复杂度为 O(n*n)，而第二种方法是使用额外的空间来保存数组中除子数组外的已排序部分。第二种方法的时间复杂度更好，即 O(nlogn)。
问题陈述
给定一个正整数数组“nums”和该数组的两个索引（即左索引和右索引），我们需要对数组进行部分排序。
我们的任务是以升序对给定的数组“nums”进行排序，但左索引和右索引之间表示的子数组应保持不变。
换句话说，子数组的元素应该与在对数组执行任何操作之前的位置相同。
示例 1
Input array: nums[] = {18, 1, 12, 6, 16,10}
left = 1
right = 3
Resultant array: {10, 1, 12, 6, 18, 16}
在这里，我们在保持子数组 arr[1…3] 的元素在相同位置的同时对数组 nums 进行了排序。
示例 2
Input array: nums[] = { 1, 8, 6, 2, 4}
left = 2
right = 3
Resultant array: {1, 4, 6, 2, 8}
方法 1：蛮力法
这种方法将数组分为三部分：左部分、右部分和子数组本身。
在这种方法中，我们首先会对给定数组的左部分进行排序，即从索引 0 到给定范围的下限的数组。在 for 循环内，我们将分别对给定数组的左部分和右部分进行排序。之后，我们将对子数组的右部分进行排序。
示例
以下是上述方法的 C++ 实现：
#include <bits/stdc++.h>
using namespace std;
void sortingexceptsubarray (int nums[], int size, int left, int right){
int iterator, j;
for(iterator = 0; iterator<left; iterator++) {
for(j = iterator+1; j<left; j++) {
if(nums[iterator] > nums[j])
swap(nums[iterator], nums[j]);
}
for (j = right+1; j<size; j++) {
if(nums[iterator] > nums[j])
swap(nums[iterator], nums[j]);
}
}
for (iterator = right+1; iterator<size; iterator++) {
for (j = iterator+1; j<size; j++) {
if(nums[iterator] > nums[j])
swap(nums[iterator], nums[j]);
}
}
}
int main(){
int nums[] = { 15,5,8,6,16,11 };
int size = sizeof(nums) / sizeof(nums[0]);
int left = 1, right = 3;
sortingexceptsubarray(nums, size, left, right );
for (int iterator = 0; iterator<size; iterator++) {
cout<<nums[iterator]<<" ";
}
}
输出
编译后，上述 C++ 程序将产生以下输出：
11 5 8 6 15 16
方法 2
在这里，我们将使用额外空间来解决给定的问题。我们将使用另一个数组来执行此方法。
首先，我们将复制数组中除子数组中存在的元素外的所有元素到一个单独的数组中。现在，我们将以升序对新的子数组进行排序，最后，我们将把元素复制并粘贴到原始数组中，以获得最终的部分排序数组。
算法
步骤 1 - 创建一个大小为 N - (上限 - 下限 + 1) 的新数组副本。
步骤 2 - 使用原始数组中的元素填充新数组“copy”，但排除给定索引的范围。
步骤 3 - 现在，我们将以升序对数组“copy”进行排序。
步骤 4 - 将数组“copy”中的元素复制到我们的原始数组“nums”，但排除通过索引给定的范围。
步骤 5 - 返回新数组并打印它。
让我们现在使用这种方法检查一个示例：
Input array: nums[] = { 1, 8, 6, 2, 4}
left = 2
right = 3
解释
创建了一个大小为 3 的数组“copy”；
将数组的所需元素复制到“copy”。
数组“copy”将是：{1, 8, 4}。
对数组“copy”排序后，我们得到：{1, 4, 8}
将排序后的数组“copy”复制到原始数组“nums”，但排除索引：2,3
最终生成的数组“nums”是：{1, 4, 6, 2, 8}
示例
以下是使用 C++ 的上述方法的实现。
#include <bits/stdc++.h>
using namespace std;
void sortExceptUandL(int num[], int lowerbound, int upperbound, int N){
int copy [N - (upperbound - lowerbound + 1)];
for (int iterator = 0; iterator < lowerbound; iterator++)
copy[iterator] = num[iterator];
for (int iterator = upperbound+1; iterator < N; iterator++)
copy[lowerbound + (iterator - (upperbound+1))] = num[iterator];
sort (copy, copy + N - (upperbound - lowerbound + 1));
for (int iterator = 0; iterator < lowerbound; iterator++)
num[iterator] = copy[iterator];
for (int iterator = upperbound+1; iterator < N; iterator++)
num[iterator] = copy [lowerbound + (iterator - (upperbound+1))];
}
int main(){
int num[] = { 5, 4, 3, 12, 14, 9 };
int N = sizeof(num) / sizeof(num[0]);
int lowerbound = 2, upperbound = 4;
sortExceptUandL(num, lowerbound, upperbound, N);
for (int iterator = 0; iterator < N; iterator++)
cout << num[iterator] << " ";
}
输出
编译后，上述程序将产生以下输出：
4 5 3 12 14 9
此方法的时间复杂度为 O(n*logn)。此方法的空间复杂度为 O(n)。
在本文中，我们学习了两种不同的方法来执行给定的任务，即排序给定的数组，忽略给定下限和上限范围之间形成的子数组。
406 次浏览
