2 smallest numbers in an array
The question is simple (the answer is also probably): How to find the two lowest numbers of an array?
for ( i = 1; i <= n ; i++){
if(v[i] < maxim)
maxim = v[i];
}
cout << maxim;
This is the only thing that comes to my mind, but it only shows the lowest number, not the two lowest numbers.
source to share
If your array can be changed, you can use std::partial_sort
:
std::partial_sort(v, v+2, v+n);
Then v[0]
and v[1]
are the two smallest values v
.
If modifying the array is not intended or should be avoided, std::partial_sort_copy
is your friend. Let's introduce a new array of two elements, into which the minima should be written:
int minima[2];
std::partial_sort_copy(v, v+n, minima, minima+2);
(Please change the array type minima
accordingly. I don't know the type of your array v
.)
For these functions to be available, you must include the following file:
#include <algorithm>
source to share
How to find k
the smallest elements of an array in C ++.
Naive method: call std::sort
; Look at the elements first k
. Execution time O (n log n).
Poll Question Method: Number the array using std::set
(or std::push_heap
and pop_heap
) with elements k
to keep track of the lowest k
. The running time is O (n log k). Also does not modify the array, returns results in order, and only uses O (k) extra space.
The best way to: #include <algorithm>
. std::nth_element(&a[0], &a[k], &a[n])
... Look at the elements first k
. Running time O (n), which is optimal.
[Update]
It seems to me that I should explain what I mean by "polling method". If you did ask this question in an interview, you are probably on Google or Amazon or some other big data-yadda-yadda environment and the interviewer said something like, “I have 100 billion integers in disk and I want to know the smallest ones. " In this context, solutions that modify the array or that require O (n) extra space are probably not the best idea.
source to share
You can use std :: sort () to sort items
Here's a quick example showing how sorting works?
#include <iostream>
#include <array>
#include <algorithm>
int main() {
std::array<int, 5> arr {5,3,24,9,7};
std::sort(arr.begin(), arr.end());
std::cout << arr[0] << std::endl << arr[1];
return 0;
}
The above code std::sort
sorts the array arr
in ascending order. <algorithm>
requires a header to use sort
.
The output will be
3
five
Here is a link to the working version of the code above.
source to share
Without changing the order of the array
#include <iostream>
#include <vector>
#include <algorithm>
int main( )
{
std::vector<int> v {9, 8, 7, 6, 5, 1, 2, 3, 4};
int smallest = *std::min_element(v.begin(), v.end());
int second_smallest = *std::min_element(v.begin(), v.end(), [&smallest](int i, int j) { return i < j && i >= smallest; });
std::cout << "smallest: " << smallest << std::endl;
std::cout << "second smallest: " << second_smallest << std::endl;
}
Output:
smallest: 1
second smallest: 2
source to share