数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学根据字符串与另一个数组元素的最大公约数 (GCD) 对字符串数组进行排序
在这个问题中，我们得到了两个字符串数组。我们需要替换array1的值来排序array1。为了替换array1的值，我们可以取array1当前字符串与array2中任何字符串的最大公约数 (GCD)。
字符串的GCD与数字的GCD非常相似。为了解决这个问题，我们可以找到一个字典序大于array1中第i个索引的字符串和array2中第j个索引的字符串的GCD的GCD字符串。
问题陈述 – 我们得到了包含字符串的array1和array2，数组的长度分别为len1和len2。我们需要通过将array1的每个元素替换为arra1[i]和array2[j]的GCD来排序array1，其中0 <= i < len1，且0 <= j < len2。如果无法通过替换array1的元素来排序数组，则需要打印-1。
注意 – 两个字符串的GCD是最小的字符串，当我们多次将其自身连接起来时，应该能够得到这两个字符串。
示例
输入 – array1 = {"aaaa", "point", "sku"}, array2 = {"pointpoint", "skuskusku"};
输出 – 是
解释 – 结果数组是 [“”, “point”, “sku”]，它按升序排序。
“aaaa”与array2中两个元素的GCD都是空字符串。
“point”与“pointpoint”的GCD是“point”。
“sku”和“pointpoint”的GCD是空字符串，它不大于前一个元素。因此，我们可以考虑“sku”和“skuskusku”的GCD，它是“sku”。
输入 – array1 = {"aacde", "acac", "aaaa"}, array2 = {"aa", "ac"};
输出 – 否
解释 – 我们可以得到的GCD结果数组是 [“”, “ac”, “aa”]，它不是按字典序排序的。
方法 1
在这种方法中，我们将array1的每个元素与array2的每个元素的GCD。之后，我们将替换字典序最小的GCD，它大于数组中当前索引之前的元素。
我们可以根据其长度的GCD来找到两个字符串的GCD。
算法
用空字符串初始化“prev”变量以存储之前的字符串
使用循环遍历array1以替换每个元素。
在循环中将当前字符串存储在“current”变量中。此外，定义“flag”变量并将其设置为true，以跟踪我们是否找到第一个大于“prev”元素的GCD元素。
现在，开始遍历array2，因为我们需要将当前元素与array2的每个元素的GCD。
在循环中，执行getStringGCD()函数以获得两个字符串的GCD。
在getStringGCD()函数中，获取两个数组的长度并使用__gcd()方法找到它们的gcd。
用空字符串初始化str1和str2。将前“gcd”个字符从字符串a附加到str1，并将前“gcd”个字符从字符串b附加到str2。
如果两个字符串中的前“gcd”个字符相等，则表示存在GCD，我们需要继续下一步。
初始化temp1和temp2字符串。
将第一个字符串附加到temp1，“(len2 / gcd)”次。
将第二个字符串附加到temp2，“(len1 / gcd)”次。
如果temp1和temp2相等，则返回“str1”，即两个字符串的GCD。
如果GCD元素大于“prev”变量的值，“flag”为true，则用gcd元素更新当前元素的值。同时，将“flag”设置为false。
如果“gcdElement”大于“prev”且“flag”为“false”，则用“current”和“gcdElement”的最小值更新“current”的值。
用“current”更新“i”的值，用“i”更新“prev”。
执行isArraySorted()函数以检查结果数组是否按升序排序。
在isArraySorted()函数中，遍历数组并检查所有第i个索引处的元素在字典序上是否小于第(i+1)个索引处的元素。
如果排序则返回array1。否则，返回空列表。
示例
#include <bits/stdc++.h>
using namespace std;
// function to get the gcd of two strings
string getStringGCD(string a, string b){
// finding the gcd of the lengths of the strings
int len1 = a.length(), len2 = b.length();
int gcd = __gcd(len1, len2);
// Initializing the strings
string str1 = "", str2 = "";
// Create two different strings of length gcd from the given strings
for (int i = 0; i < gcd; i++) {
// append total gcd characters from a[i] to str1
str1.push_back(a[i]);
}
for (int i = 0; i < gcd; i++) {
// // append total gcd characters from b[i] to str2
str2.push_back(b[i]);
}
// If the two strings are equal, then the gcd exists (The initial part of the string is the same)
if (str1 == str2) {
// Initialize two temporary strings
string temp1 = "", temp2 = "";
// append the string a to temp1 len2/gcd times, and string b to temp2 len1/gcd times to make length of both strings equal.
for (int i = 1; i <= (int)(len2 / gcd); i++) {
temp1 += a;
}
for (int i = 1; i <= (int)(len1 / gcd); i++) {
temp2 += b;
}
// If temp1 and temp2 are equal, then the gcd exists (The final part of the string is the same)
if (temp1 == temp2)
return str1;
}
// return an empty string if gcd does not exist
return " ";
}
// function to check whether the array is sorted or not
bool isArraySorted(vector<string> array) {
// Traverse the array
for (int i = 0; i < array.size() - 1; i++) {
// If we find any string at index i is greater than or equal to the next string, then the array is not sorted
if (array[i] >= array[i + 1])
return false;
}
// If the array is sorted, then return true.
return true;
}
// function to sort the array if possible
vector<string> sortStrings(vector<string> array1, vector<string> array2) {
// Previous string
string prev = "";
// Iterate through the array
for (string &i : array1) {
// Initialize the current string
string current = i;
// flag to find the first string greater than the prev
bool flag = true;
// Iterate through the array2
for (string j : array2){
// Get the gcd of I and j strings
string gcdElement = getStringGCD(i, j);
// If the Gcd element is greater than prev and the flag is true
if (gcdElement > prev && flag) {
// Update the current string
current = gcdElement;
// set flag to false
flag = false;
}
// If gcdElement > prev and flag is false
if (gcdElement > prev){
// Update the current string
current = min(current, gcdElement);
}
}
// Update array1[i] by current
i = current;
// Update prev by array1[i]
prev = i;
}
// check is array1[] is sorted in ascending order
if (isArraySorted(array1)) {
return array1;
}
// Sorted order is not possible
vector<string> ans;
return ans;
}
int main() {
vector<string> array1 = {"aacde", "acac", "aaaa"};
vector<string> array2 = {"aa", "ac"};
vector<string> ans = sortStrings(array1, array2);
// If the size of ans is 0, then it is not possible to sort the array
if (ans.size() == 0) {
cout << "It is not possible to sort the array in ascending order.";
} else {
cout << "The array of strings after replacing with their GCD in the sorted order is: ";
for (string str : ans) {
cout << str << ", ";
}
}
return 0;
}
输出
It is not possible to sort the array in ascending order.
时间复杂度 – O(len1 * len2 * log(min(len3, len4)))，其中len1是array1的长度，len2是array2的长度。len3是array1中任何字符串的最大长度，len4是array2中任何字符串的最大长度。
空间复杂度 – O(1)，因为我们没有使用任何常量空间。
68 次查看
