資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法學研究在不改變母音位置的情況下對字串進行排序
字串排序是指我們將給定的字串按升序、降序或任何給定的順序排列。在這個問題中，給定一個大小為 n 的字串 'str'。我們的目標是在不改變字串中母音位置的情況下對給定的字串進行排序。
讓我們看看下面的例子和解釋，以便更好地理解這個問題。
示例
輸入1
str = “abdecokfee”
輸出1
abcedofkee
解釋
字串中存在的子音 = bdckf
對子音字串排序 = bcdfk
將給定的字串與排序後的子音字串合併，而不改變母音的位置 = abcedofkee
輸入2
str = str = “hellothere”
輸出2
str = hehlolrete
解釋
字串中存在的子音 = hllthr
對子音字串排序 = hhllrt
將給定的字串與排序後的子音字串合併，而不改變母音的位置 = hehlolrete
方法 1：樸素方法
這個想法很簡單，首先將給定字串的所有子音儲存到變數字串 'temp' 中，然後使用 sort 函式對這個 temp 字串進行排序。最後，用排序後的子音字串字元替換給定字串的子音字元，而不改變給定字串中母音的位置。
示例
讓我們看看下面的程式碼，以便更好地理解上述方法。下面是一個用於在不改變母音位置的情況下對字串進行排序的 C++ 程式。
#include <bits/stdc++.h>
using namespace std;
// Created a function to sort the constant char of the string
string sortString(string str, int n){
string temp = ""; // Stroing the constant string
// Traverse the string using for loop to get constant
for( int i=0; i<n; i++ ){
// IF char is not vowel add to char the string temp
if( str[i] != 'e' && str[i] != 'o' && str[i] != 'a' && str[i] != 'u' && str[i] != 'i' ){
temp += str[i];
}
}
// If temp string has character
if(temp.size()){
// Sort the constant string using sort function
sort( temp.begin(), temp.end() );
}
int idx = 0; // to traverse the constant sorting sring
// Traverse the string using for loop to get resultant
for( int i=0; i<n; i++ ){
// IF char is not vowel add to char the string temp
if( str[i] != 'e' && str[i] != 'o' && str[i] != 'a' && str[i] != 'u' && str[i] != 'i' ){
// Replace sorted constant with given string constant
str[i] = temp[idx];
idx++; // Increment the pointer of the sorted constant string
}
}
// Return the resultant
return str;
}
int main(){
string S = "abdecokfee"; // Given string
int N = S.size(); // Gettig the size of the string
// Call the function
string result = sortString(S, N); // Store the sorted string
// Print the string
cout << "The sorted string without changing the position of the vowel is " << result;
return 0;
}
輸出
The sorted string without changing the position of the vowel is abcedofkee
時間和空間複雜度
由於我們使用排序函式對子音字串進行排序，所以上述程式碼的時間複雜度為 O(N*(logN))。
上述程式碼的空間複雜度為 O(N)，因為我們將子音字元儲存在新字串 temp 中。
其中 N 是字串的大小。
方法 2
在上面的程式碼中，我們使用了一個新字串來儲存給定字串的子音字元，並使用 sort 函式對其進行排序，但是我們可以使用大小為 26 的對映來代替這樣做，它也可以按排序方式儲存字元。
示例
下面是一個用於在不改變母音位置的情況下對字串進行排序的 C++ 程式。
#include <bits/stdc++.h>
using namespace std;
// Function to sort the constant char of the string
string sortString(string str, int n){
map<char, int>mp; // Stroing the constant of the string
// Traverse the string using for loop to get constant
for( int i=0; i<n; i++ ){
// IF char is not vowel add to char the string temp
if( str[i] != 'e' && str[i] != 'o' && str[i] != 'a' && str[i] != 'u' && str[i] != 'i' ){
mp[ str[i] ]++;
}
}
// Check whether constant is present or not
if(mp.size() <= 1) return str;
int idx = 0; // to traverse the given string
// Traverse the map
for( auto &x : mp){
// While the current char exist
while(x.second){
while( str[idx] == 'e' || str[idx] == 'u' || str[idx] == 'a' || str[idx] == 'i' || str[idx] == 'o' ){
idx++; // Increment the pointer of a given string
}
// Replace sorted constant with given string constant
str[idx] = x.first;
idx++; // Increment the pointer of a given string
x.second--; // Decrement the current char
}
}
// Return the resultant
return str;
}
// Driver Code
int main(){
string S = "abdecokfee"; // Given string
int N = S.size(); // Gettig the size of the string
// Call the function
string result = sortString(S, N); // Store the sorted string
// Print the string
cout << "The sorted string without changing the position of the vowel is " << result;
return 0;
}
輸出
The sorted string without changing the position of the vowel is abcedofkee
時間和空間複雜度
時間複雜度：O(N*(logN))。因為我們遍歷了對映。
空間複雜度：O(1)，因為對映的大小是常數 26。
其中 N 是字串的大小。
結論
在本教程中，我們實現了一個程式來查詢在不改變母音位置的情況下對字串進行排序的方法。我們實現了兩種方法：使用排序函式的樸素方法和使用雜湊對映的高效方法。兩種方法的時間複雜度均為 O(N*(logN))，空間複雜度分別為 O(N) 和 O(1)。其中 N 是字串的大小。
455 次瀏覽
