I want to find the next minimum value in a one-dimensional array so that I don't want to sort the array first.
For example if I have this array:
int [] a={10,5,20,3};
The first minimum value is 3, the second is 5, the third is 10 and the last is 20.
Now I want to know the index number of minimum values respectively. What is the index number of the first minimum value and index number of the second minimum value, and the index number of the third value ...
How can do it I in c#?
I think that by using two loops and traversing the presentation, it is possible to determine the next minimum value.
CodePudding user response：
I have an array
for example int [] a={10,5,20,3}
The first minimum value is 3, the second one is 5, the third one is 10 and the last one is 20. Now I want to know the index number of each minimum value respectively. What is the index number of the first minimum value and index number of the second minimum value, and the index number of the third value ...
CodePudding user response：
class Program
{
static void Main(string[] args)
{
int[] a = { 10, 5, 20, 3 };
int[] aCopy = new int[a.Length];
Array.Copy(a, aCopy, a.Length);
Array.Sort(aCopy);
var result = string.Empty;
foreach(int value in aCopy)
{
result = $"({value}, {Array.IndexOf(a, value)})\n";
}
Console.WriteLine(result);
}
}
CodePudding user response：
Use a method that gets the array and finds the minimum value in the array based on a known maximum. The call that method in a loop to get the first, second, third and so on minimum in sequence. Always use the determined minimum from the previous loop as the know maximum in the next loop.
internal class Program
{
/// <summary>
/// Finds the minimum value in values that is bigger than knownMaximum
/// </summary>
/// <returns>´Found minimum value and zero-based position</returns>
static (int? minValue, int? position) GetNextMinimum(int[] values, int? knownMaximum)
{
int? minValue = null;
int? position = null;
for(int i=0; i< values.Length; i )
{
int value = values[i];
// If the current value is bigger than knownMaximum or no know Maximum specified
if(!knownMaximum.HasValue || value > knownMaximum.Value )
{
// If current value is smaller than minimum value so far
if(!minValue.HasValue || value < minValue.Value)
{
// Remember current value and position as minimum
minValue= value;
position= i;
}
}
}
return (minValue, position);
}
static void Main(string[] args)
{
int[] values = { 10, 5, 20, 3 };
int? knownMaximum = null;
// Get 1st, 2nd and 3rd Minimum
for (int i=1; i<=3; i )
{
var (minValue, position) = GetNextMinimum(values, knownMaximum);
Console.WriteLine($"{i}\t Position {position}\t Value {minValue}");
// Use the current minValue as known Maximum for nect round
knownMaximum = minValue;
}
}
}
CodePudding user response：
Yes it is possible with tow loop. I don't know C# syntax but i can give you the answer in C :
int next_min (int* array ,int sizeofarray)
{
int i , fmin , smin;
fmin = array[0];
for (i=0 , i<sizeofarray , i )
{
if (array[i]<fmin)
{
fmin = array[i];
}
}
smin = array[0];
for (i=0 , i<sizeofarray , i )
{
if (array[i]<smin && smin !=fmin)
{
min = array[i];
}
}
return smin ;
}
CodePudding user response：
With a stack an get a O(n) complexity, the idea is to
maintain items in increasing order in the stack.
Push the first element to stack.
Pick rest of the elements one by one and follow following steps in loop. Mark the current element as next. If stack is not empty, then compare next with stack top. If next is smaller than top then next is the NSE for the top. Keep popping from the stack while top is greater than next. next becomes the NSE for all such popped elements Push next into the stack
After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them
Here is a code that helps:
/* prints element and NSE pair for all
elements of arr[] of size n */
public static void printNSE(int[] arr, int n)
{
Stack <int> s = new Stack <int>();
Dictionary <int,int> mp= new Dictionary <int,int>();
/* push the first element to stack */
s.Push(arr[0]);
// iterate for rest of the elements
for (int i = 1; i < n; i ) {
if (s.Count == 0) {
s.Push(arr[i]);
continue;
}
/* if stack is not empty, then
pop an element from stack.
If the popped element is greater
than next, then
a) print the pair
b) keep popping while elements are
greater and stack is not empty */
while (s.Count != 0 && s.Peek() > arr[i]) {
mp.Add(s.Peek(), arr[i]);
s.Pop();
}
/* push next to stack so that we can find
next smaller for it */
s.Push(arr[i]);
}
/* After iterating over the loop, the remaining
elements in stack do not have the next smaller
element, so print -1 for them */
while (s.Count != 0) {
mp.Add(s.Peek(), -1);
s.Pop();
}
for (int i = 0; i < n; i )
Console.WriteLine(arr[i] " ---> " mp[arr[i]]);
}
// Driver code
public static void Main()
{
int[] arr = { 11, 13, 21, 3};
int n = arr.Length;
printNSE(arr, n);
}