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.
Another easy way: ..
int v[] = {33,11,22,3};
int secmaxim = INT_MAX-1;
int maxim = INT_MAX;
for ( int i = 0; i < 4 ; i++){
if(v[i] < maxim)
{
secmaxim = maxim;
maxim = v[i];
}
else if(v[i] < secmaxim && v[i] != maxim)
secmaxim = v[i];
}
cout << maxim << secmaxim;
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>
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.
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.
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
Adapted from @ leemes answer (using more modern syntax) see his answer for an explanation.
const auto topVals = 2;
std::array<int, topVals> minima;
std::partial_sort_copy(std::begin(v), std::end(v), minima.begin(), minima.end());