資料結構
網路
關係資料庫管理系統 (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 次瀏覽
