Является ли _ (одиночное подчеркивание) допустимым именем переменной C ++?

вам нужно будет найти k'th наименьший элемент, используя «алгоритм выбора», который является O (n), а затем снова итерации массива и возврата каждого элемента, который меньше / равен ему. алгоритм выбора: http://en.wikipedia.org/wiki/Selection_algorithm вам придется обратить внимание, если у вас есть повторы: вам нужно будет убедиться, что вы не возвращаете больше k элементов (это возможно, если вы, например, имеете 1,2, ..., k, k, k, ...) EDIT: полный алгоритм и возвращающий список в соответствии с запросом: пусть массив будет A

 1. find the k'th element in A using 'selection algorithm', let it be 'z'
 2. initialize an empty list 'L'
 3. initialize counter<-0
 4. for each element in A: 
 4.1. if element < z: 
   4.1.1. counter<-counter + 1 ; L.add(element)
 5. for each element in A:
 5.1. if element == z AND count < k:
   5.1.1. counter<-counter + 1 ; L.add(element)
 6. return L

обратите внимание, что требуется 3-я итерация, если в вашем списке могут быть дубликаты. если он не может - это бесполезно, просто измените условие в 4.1 на & lt; =. также обратите внимание: L.add вставляет элемент в связанный список и, следовательно, O (1).