資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告