函数在使用集合时返回错误的第k个值

Question

我试图在一些网站上解决这个问题，在那里你可以找到c++中的第k个最小值，所以我想到了:

#include <bits/stdc++.h>
using namespace std;
int kthSmallest(int arr[], int l, int r, int k) {
// l is the first index 
// r is the index of the last element (size - 1)
// k is the kth smallest value 
set<int> s(arr, arr + r); 

set<int>:: iterator itr = s.begin();
advance(itr, (k - 1));

return *itr;
}
int main() {
int arr[] = {7, 10, 4, 20, 15};
cout << kthSmallest(arr, 0, 4, 4);
return 0;
}

这显示的输出是20而不是15，这是正确的答案，我不知道我在这里做错了什么。

Answer 1

std::set的构造函数的第二个参数应该是最后一个元素旁边的元素的迭代器，而不是最后一个元素的迭代器。

因此，你在操作一个成员为{7, 10, 4, 20}的集合。

行

set<int> s(arr, arr + r);

应该

set<int> s(arr, arr + r + 1);

或者(为了匹配注释)

set<int> s(arr + l, arr + r + 1);

Answer 2

语句的范围

set<int> s(arr, arr + r);

数组的r等于4

时，指定不正确

int arr[] = {7, 10, 4, 20, 15};

有5个元素。这意味着15不存在于[7, 10, 4, 20]范围内。您必须指定参数r等于5，即数组中的元素数量，而不是4。

函数中也没有使用参数l

检查k的值是否大于r调用函数std::advance的值

还要注意数组可以有重复的值。在这种情况下，函数可能返回一个不正确的值。

所以一般来说你的函数是不正确和不安全的。

不是返回int类型的对象，而是返回一个迭代器，该迭代器指向数组中的目标对象，或者指向范围的末端或目标元素的索引。

使用你的方法，你应该使用std::multiset而不是std::set。并且k的值应该从0开始作为c++中的所有索引。否则调用k的值等于0的函数，您将得到未定义的行为。

这是一个示范程序。

#include <iostream>
#include <functional>
#include <set>
#include <iterator>
size_t kthSmallest( const int arr[], size_t n, size_t k ) 
{
if ( not ( k < n ) ) return n;
std::multiset<std::reference_wrapper<const int>> s;
for ( size_t i = 0; i < n; i++ )
{
s.insert( std::ref( arr[i]) );
}
auto it = std::next( std::begin( s ), k );
size_t result = std::distance( arr, &it->get() );
return result;
}    
int main() 
{
int arr[] = {7, 10, 4, 20, 15};
const size_t N = sizeof( arr ) / sizeof( *arr );
for ( size_t i = 0; i < N; i++ )
{
std::cout << i << ": " << arr[kthSmallest( arr, N, i )] << 'n';
}
return 0;
}

程序输出为

0: 4
1: 7
2: 10
3: 15
4: 20