极客笔记C++ 通过交换相邻的偶-奇对获得的最小数字
“偶-奇对”意味着一对连续的整数，其中一个是偶数，另一个是奇数。例如，偶-奇对包括（2, 3），（4, 5），（6, 7）等。
这些配对通常在基于数字变换的算法和编程练习中使用。在重复一组数字时，可能只想对偶数或奇数进行操作。当出现这种情况时，使用偶-奇对可以通过减少所需的条件语句的数量来简化代码。
方法
通过交换相邻的偶-奇配对，您可以应用以下策略来确定最小可能的数字 −
- 冒泡排序方法
-
贪心法
方法1：冒泡排序方法
从数字开始，我们必须使用类似冒泡排序的算法来解决问题。从开始，我们必须仔细检查每一对相邻数字。如果一对数字中的左边是奇数，右边是偶数，我们交换它们的位置。在处理完最后两个数字后，该过程继续进行到下一个数字。如果在整个循环期间发生了任何变化，我们必须重新开始整个过程。
语法
要通过交换相邻的偶-奇对来获得最小数字，请按照以下步骤在C++中构建冒泡排序算法的教程 −
- 创建整数数组并填充要排序的数字。
int q[] = {6, 4, 2, 5, 7, 1};
- 计算数组的大小或长度。
int p = sizeof(q) / sizeof(q[0]);
- 应用冒泡排序算法。
for (int r = 0; r < p - 1; r++) {
for (int j = 0; j < p - r - 1; j++) {
if (q[j] % 2 == 0 && q [j + 1] % 2 != 0) {
swap(q[j], q [j + 1]);
}
}
}
- 输出排序后的数组。
for (int r = 0; r < p; r++) {
cout << q[r] << " ";
}
步骤
通过交换相邻的偶-奇对，使用冒泡排序法找到最小数的逐步算法 −
步骤 1 − 输入一组需要排序的数字。
步骤 2 − 创建一个循环，重复遍历数组直到所有元素都已排序。
步骤 3 − 在第一个循环内部创建第二个循环，遍历数组中的每一对相邻元素。
步骤 4 − 对于每一对相邻元素，判断第一个元素是否为奇数，第二个元素是否为偶数。如果是，则交换这两个元素。
步骤 5 − 如果数组中存在先前的元素，将新交换的元素与它进行比较。根据需要，用更小的元素替换先前交换的元素。
步骤 6 − 迭代遍历整个数组，直到每一对元素都经过验证和排序。
步骤 7 − 如果在任何迭代过程中没有进行交换，认为数组已经排序完成，并结束外部循环。
步骤 8 − 排序完成后，打印已排序的数组。
示例1
为了通过交换相邻的偶-奇对得到最小数，下面是C++中使用冒泡排序法的示例实现 −
使用向量，通过应用冒泡排序算法的冒泡排序方法，在该实现中对输入数字进行排序。交换变量用于跟踪内循环中的交换次数。如果一次遍历完成且没有进行任何交换，算法停止运行，利用已经排序好的列表。
在内循环中，我们比较每一对相邻的数字。只有当第一个数字是奇数，第二个数字是偶数，或者当数字的奇偶性匹配且第一个数字较大时，我们才修改数字。偶数在奇数之前的顺序会使得偶-奇对以升序排列。
使用for循环，打印输出是已排序的数字。如果在相邻数字之间进行偶-奇配对的修改，结果将是产生最小可能的序列2 7 5 8 9 10 1 12。
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& nums) {
int n = nums.size();
bool swapped;
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = 0; j < n-i-1; j++) {
if ((nums[j] % 2 == 0 && nums[j+1] % 2 != 0) || (nums[j] % 2 == nums[j+1] % 2 && nums[j] > nums[j+1])) {
swap(nums[j], nums[j+1]);
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
vector<int> nums = {7, 2, 5, 9, 12, 10, 8, 1};
bubbleSort(nums);
for (int num : nums) {
cout << num << " ";
}
cout << endl; // Output: 2 7 5 8 9 10 1 12
return 0;
}
输出
1 5 7 9 2 8 10 12
方法2：贪心算法
另一种策略是始终用后面最大的奇数位替换最小的偶数位。这被称为贪心算法。找到最左侧偶数位右侧的最大奇数位。在这种情况下，交换这两个数字，并继续下一步，从交换后的偶数位开始。如果当前偶数位右侧没有更大的奇数位，则使用下一个偶数位。
语法
这是一个逐步实现贪心方法的C++代码，通过交换相邻的偶奇对来找到可能的最小数 –
- 定义一个函数来交换字符串中相邻的两个字符 –
void swapAdjacentChars(string& s, int i) {
char temp = s[i];
s[i] = s[i+1];
s[i+1] = temp;
}
- 初始化字符串
string s = "98167375";
- 循环遍历字符串，交换相邻的偶数-奇数对
for (int o = 0; o < s.l () - 1; o++) {
if ((s[o] - '0') % 2 == 0 && (s[o+1] - '0') % 2! = 0) {
swap Adjacentn Chars (s, o);
break;
}
}
- 打印结果
cout << s << endl;
}
步骤
使用贪婪算法找到通过交换相邻的偶-奇对产生的最小数字可以按照以下步骤进行实现−
步骤1 − 将给定的数字转换为数字数组。
步骤2 − 从左到右遍历数组，对于每个偶数位，搜索右侧最小的奇数位。
步骤3 − 如果找到了较小的奇数位，交换偶数和奇数位，并且打破循环。
步骤4 − 如果没有找到较小的奇数位，继续到下一个偶数位。
步骤5 − 将数字数组转换为一个单一的数字似乎是一项具有挑战性的任务。然而，将交换算法应用于这个问题可以提供O(n^2)的时间复杂度，其中n表示初始数字中的位数。幸运的是，所需的交换次数通常很少；因此，该解决方案既高效又快速。
示例2
下面是一个使用贪婪方法的C++示例，其中我们交换相邻的偶-奇对来获得最小的整数−
在这个示例中，我们创建了一个名为”smallest number”的函数，它以一个字符串”num”作为输入，并返回通过交换相邻的偶-奇对形成的最小数字。该方法第一次迭代字符串时，确定当前索引是否为偶数，并且该位置的数字为奇数。在这种情况下，它在字符串中寻找后面的偶数位，并将它与奇数位交换。函数将修改后的字符串作为输出返回。
#include <iostream>
#include <string>
using namespace std;
string smallestNumber(string num) {
int n = num.length();
// Iterate over the string and swap adjacent even-odd pairs
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0 && num[i] % 2 != 0) {
// Swap the current odd digit with the next even digit
for (int j = i + 1; j < n; j++) {
if (j % 2 != 0 && num[j] % 2 == 0) {
swap(num[i], num[j]);
break;
}
}
}
}
return num;
}
int main() {
string num = "2145367";
cout << "Original number: " << num << endl;
cout << "Smallest number possible: " << smallestNumber(num) << endl;
return 0;
}
输出
Original number: 2145367
Smallest number possible: 2145637
结论
从最左边的数字开始，我们可以将其与相邻的数字进行比较，以找到通过改变相邻的偶数-奇数配对而获得的最小值。为了创建这个最小数字，如果左边的数字是偶数且右边的数字是奇数，我们会交换这两个数字。这个过程会一直持续到最右边的数字。通过这种方法，我们可以确保较小的数字首先出现在数字中，从而使其成为可以实现的最小数字。如果存在几个相同值的偶数-奇数配对，我们首先必须考虑最靠近最左边的配对。