C++ 对给定数组的字符串进行排序，排序时删除字符的频率不是2的幂次方

在这个问题中，我们需要删除字符串中频率不是2的幂次方的字符，然后按非递增顺序对数组中的每个字符串进行排序。

问题陈述 - 我们给定一个包含N个不同长度的字符串的数组arr[]。如果字符串中的字符频率不是2的幂次方，则需要删除该字符。之后，我们需要对每个字符串进行排序。

示例示例

输入 - arr[] = {“abde”, “cpcc”, “ddddd”, “kk”}

输出 - edba, p, kk

解释

• 在字符串’abde’中，所有字符的频率都是1，等于2的0次方。

• 在字符串’cpcc’中，’c’的频率为3，不等于任何2的幂次方。所以我们把它删除了。

• 在字符串’ddddd’中，’d’的频率是5。所以从字符串中删除了所有字符。

• 在字符串’kk’中，’k’的频率是2，等于2的1次方。

最后，我们按降序对所有字符串进行了排序，并显示了非空字符串。

输入 - arr[] = {“yz “, “nm”, “”, “”}

输出 - zy, mn

解释 - 它从输出中删除了空字符串。

方法1

在这个方法中，首先，我们将计算给定字符串中每个字符的频率。然后，我们将检查频率是否是2的幂次方。如果是，则将字符保留在字符串中。否则，我们将从字符串中删除它。

以下算法可用于解决该问题。

步骤

• 定义isPowerOfTwo()函数来检查一个数字是否是2的幂次方。
  • 在函数中，如果’num’等于零，则返回false。

  • 保持2为底的对数并将其取整得到一个数字log。

  • 如果num是2的幂次方，当我们取对数时，我们得到一个整数值。因此，使用ceil()和floor()方法来检查对数值是否是整数，并根据此返回布尔值。

• 定义sorted String()函数，对修改后的字符串进行排序

• 定义’freq’映射，用于存储特定字符串字符的频率。同时，定义’ans’向量，用于存储结果字符串。

• 使用循环遍历字符串数组。在循环中，定义’temp’字符串变量并初始化为空字符串。

• 现在，使用循环从第i个索引开始遍历字符串，并将其字符的频率存储在’freq’映射中。

如果是2的幂，则将字符频率添加到temp字符串中。

• 使用clear()方法清除映射，因为我们需要存储另一个字符串的字符频率。

• 如果’temp’字符串的大小为零，则继续迭代。

• 使用sort()方法对字符串进行排序，并将其附加到’ans’向量中。

• 遍历’ans’向量以获取所有结果字符串。

示例

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
using namespace std;

// Check whether Num is power of 2
bool isPowerOfTwo(int num){
   // Base Case
   if (num == 0)
      return false;
   // If num is a power of 2, then log2(num) will be an integer value.
   return (ceil(log2(num)) == floor(log2(num)));
}
// function to modify the array of strings according to the given condition.
void sortedStrings(string str[], int N){
   // map to store the frequency of each alphabet of the string.
   unordered_map<char, int> freq;
   // storing answer in a vector of strings.
   vector<string> ans;
   // iterate over the array of strings
   for (int i = 0; i < N; i++){
      // Temporary string
      string temp = "";
      // Stores frequency of each
      // alphabet of the string
      for (int j = 0; j < str[i].size(); j++){
         // Update frequency of str[i][j]
         freq[str[i][j]]++;
      }
      // Iterate over the map
      for (auto i : freq){
         // If the frequency of any alphabet is a power of 2, then append it to temp.
          if (isPowerOfTwo(i.second)){
             // append i.first character i.second times to temp.
             for (int j = 0; j < i.second; j++){
                 temp += i.first;
             }
          }
      }
      // Clear the map
      freq.clear();
      // empty string
      if (temp.size() == 0)
         continue;
      // sort the string in non-increasing order
      sort(temp.begin(), temp.end(), greater<char>());
      // push temp string to ans
      ans.push_back(temp);
   }
   // Print the array of strings
   cout << "The array of strings after modification is: ";
   for (int i = 0; i < ans.size(); i++){
      cout << ans[i] << " ";
   }
}
int main(){
   string arr[] = {"abde", "cpcc", "ddddd", "kk"};
   int N = sizeof(arr) / sizeof(arr[0]);
   sortedStrings(arr, N);
   return 0;
}

输出

The array of strings after modification is: edba p kk

时间复杂度 – O(N*M)，其中N是数组的长度，M是字符串的最大长度。

空间复杂度 – O(N)，用于在映射中存储字符频率。

我们学会了从字符串中删除所有频率不等于2的幂次的字符，并按照递减顺序对字符串进行排序。程序员可以尝试按照字符频率的顺序对字符串进行排序。