Topic describes

[topic address]

Given an array of integers, write a function to find the indexes m and n. The array is sorted as long as the elements of the index interval [m,n] are sorted. Note: n-m should be as minimal as possible, that is, find the shortest sequence that meets the condition. The function returns [m,n], or [-1,-1] if no such m and n exist (for example, if the entire array is ordered).

Example:

Output: input:,2,4,7,10,11,7,12,6,7,16,18,19 [1] [3, 9]Copy the code

Tip:

  • 0 <= len(array) <= 1000000

Their thinking

We can first from left to right to find the right border, record already handle your maximum range, if found in subsequent traversal process is smaller than the maximum value of a value, that at this point the former after the small, show that the location is a need to sort, update n equals the subscript, so after a scan to determine the right boundary n. Similarly, the left boundary can be found from right to left, m = len-1 (len is the length of the input array) is initialized, and the minimum value in the processed interval is recorded. If a value is found larger than the minimum value, it indicates that the first value is large and then the second value is small, indicating that this position needs to be sorted, then the left boundary m is updated as the subscript. This scan determines the left boundary m. In this way, we determine m and n by traversing the number group twice, and finally judge whether [m,n] is legal. If so, return [m,n], otherwise return [-1,-1.

The demo

Code implementation

var subSort = function(array) { let r = -1, l = -1; Let Max = number.min_safe_INTEGER; let Max = number.min_safe_integer; For (let I = 0; i < array.length; i++){ if(array[i] >= max){ max = array[i]; }else{ r = i; }} // let min = number. MAX_SAFE_INTEGER; for(let i = array.length - 1; i >= 0; i--){ if(array[i] <= min){ min = array[i]; }else{ l = i; } } return [l , r]; };Copy the code

At this point we have completed leetcode- Interview question 16.16- part sorting