数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 O(1) 额外空间按相同顺序查找最小的 k 个元素
我们有一个包含“size”个元素的数组“nums”和一个整数“number”，表示我们必须返回的最小的元素的数量。我们的任务是从给定数组中找出“number”个最小的元素。元素的顺序应保持不变，并且我们不允许使用任何额外的变量空间来解决问题，即解决方案的空间复杂度应为 O(1)。
让我们用一个例子来理解这一点，
nums = { 4, 2, 6, 5, 1 }
解决方案应该返回 4、2、5，因为它们是给定数组中最小的 3 个元素。还有一点需要注意，输出数字的顺序是 4、2、5，而不是 2、4、5，因此保持了数字的原始顺序。
输出应为 -
给定数组中最小的 3 个元素是
4 2 1
方法 1
算法背后的思想是将 k 个最小元素移动到数组的开头，同时保持其原始顺序。为了实现这一点，可以使用插入排序算法的修改版本。
以下是算法的分步说明 -
从第 ('number' +1) 个元素开始迭代到数组的末尾。
对于迭代中遇到的每个元素，将其与前 'number' 个元素中最大的元素进行比较。
如果当前元素小于前 k 个元素中最大的元素，则用当前元素替换最大的元素。
为了保持元素的顺序，通过将前 'number' 个元素中的所有元素向右移动一个位置来执行替换，丢弃以前的最大元素。
继续迭代直到数组的末尾。
示例
下面给出了在 C++ 中实现上述解决方案的代码 -
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
void smallest_three(int nums[], int size, int number){
for (int iterator = number; iterator < size; ++iterator){
int largesr_number = nums[number - 1];
int pos = number - 1;
for (int iterator_2 = number - 2; iterator_2 >= 0; iterator_2--){
if (nums[iterator_2] > largesr_number){
largesr_number = nums[iterator_2];
pos = iterator_2;
}
}
if (largesr_number > nums[iterator]){
int iterator_2 = pos;
while (iterator_2 < number - 1){
nums[iterator_2] = nums[iterator_2 + 1];
iterator_2++;
}
nums[number - 1] = nums[iterator];
}
}
for (int iterator = 0; iterator < number; iterator++){
cout << nums[iterator] << " ";
}
}
int main(){
int nums[] = { 4, 2, 6, 5, 1 };
int size = sizeof(nums) / sizeof(nums[0]);
int number = 3;
cout<< "The smallest " << number << " elements " << "of the given array are " <<endl;
smallest_three(nums, size, number);
return 0;
}
输出
The smallest 3 elements of the given array are 4 2 1
时间复杂度 - 上述代码实现的时间复杂度为 O(n^2)，因为我们使用了两个嵌套循环。
空间复杂度 - 因为我们被要求在代码中不使用任何额外的变量空间，所以它的空间复杂度为 O(1)。
更新于: 2023年10月5日
78 次查看
广告