First of all, can be seen from the subject, for most of the developers, it is a basic couldn’t be the basis of the topic, so, know how to solve, and fully grasp the process of solving, can need not to look down, if hope to be able to review, to the problem or don’t understand the words, you can then look down. My writing is a waste of readers’ time, but I only hope to explain these simple topics clearly in clear language to improve my ability of expression.

Topic describes

Given an unordered array, find the maximum and minimum value in the array.

Their thinking

For example, if you have an unordered array [3,5,7,2], you can see that this array has a maximum value of 2 and a minimum value of 7.

So how do we do that? To the maximum, we can declare a variable as the maximum value, the variable initial value for the first element of the array, and then iterate over this array, will present the maximum comparing with current traversal of the element, if the current element is larger than the variable, then update the maximum as the value of the current element.

Code implementation

Using swift code, note that the type of the element in the code should be generic and the return type should be optional, because there is no maximum or minimum value if the array is empty. The following code is used to find the maximum value in the array.

func findMax<T:Comparable>(_ array: [T]) ->T? {
    guard var max = array.first else { return nil }
    
    for element in array.dropFirst() {
        if(element > max){
            max = element
        }
    }
    return max
}
Copy the code

,5,7,2 [3] this array, for example, in the interpretation of specific, first of all, the assumption of the array first 3 for maximum, starting with the back of the 5, 5 is bigger, the update 5 for maximum, and then compared with the back of the 7, 7 is greater than 5 again, update the maximum seven, seven in comparing with 2, 7 is greater than 2, remain unchanged, the end of the cycle, 7 is the maximum value in the array.

To minimize the same idea:

func findMin<T:Comparable>(_ array: [T]) ->T? {
    guard var min = array.first else { return nil }
    
    for element in array.dropFirst() {
        if(element < min){
            min = element
        }
    }
    return min;
}
Copy the code

In addition, in the language of the standard library, may also be packaged to solve the maximum, minimum function, can be directly used.

letArray = [4,12,56,32,65,2,3,6] array.min() returns 2 array.max() // returns 65Copy the code

How do you encapsulate maximizing and minimizing in one function? In Swift, you can use tuples to return both maximum and minimum values.

Sample code:

func findMaxMin<T:Comparable>(_ array:[T]) ->(min: T,max:T)? {
    guard var min = array.first else { return nil }
    
    var max = min
    
    letStart = array.count % 2 // If the number is singular, the system starts from index = 1for i in stride(from: start, to: array.count, by: 2) {
        let pair = (array[i],array[i+1])
        
        if(pair.0 > pair.1){
            if pair.0 > max {
                max = pair.0
            }
            
            if pair.1 < min {
                min = pair.1
            }
            
        } else {
            if pair.1 > max {
                max = pair.1
            }
            
            if pair.0 < min {
                min = pair.0
            }
        }
    }
    
    return (min, max)
}
Copy the code

The overall logic of the code is not hard to understand, using arrays [3,7,2,5,9] as an example.

If the number of elements in the array is singular or even, the array is iterated from index = 1. This is because the array is iterated in pairs.

The array [3,7,2,5,9] has an odd number of elements. The first time 7 is selected,2 forms a tuple (7,2). Then 7 is compared with 2, 7 is larger than 2, so 7 is compared with the first element set to the maximum,7 is larger than 3,7 replaces 3 as the maximum. 2 is then compared to 3, which is also set to be the minimum. 2 is smaller than 3, and 2 replaces 3 as the minimum.

Proceed to the next group of 5 and 9 to form a tuple. Compare 9 with the temporary maximum value of 7 because 9 is larger than 5. 9 replaces 7 as the maximum value. 5 is then compared with the temporary minimum value 2, which is smaller than 5 and remains the current minimum value.

At the end of the loop, the current minimum value 2 and maximum value 9 form a tuple (2, 9) and are output as the return value of the function. At this point, the function ends.

In some languages that may not have tuple-like data structures, you can also use arrays, where the first element stores the minimum value and the second element stores the maximum value. Map can also be used to store key values and output them as function return values.

Time complexity analysis

We iterate through the array and take out each element for a maximum or minimum comparison, so this algorithm has O(n) time.