“This is the 17th day of my participation in the First Challenge 2022.

[B] [C] [D]

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

The simplest and most straightforward way to do this is to copy the array and sort it, and then compare the elements from left to right. The first different position is M. Similarly, compare the elements from right to left and the first different position is N. If [m,n] is valid, return [m,n], otherwise return [-1,-1. This method can solve the problem, but because of one sort and two look-up, take sort as an example, the sorting time complexity O(nlogn), the time complexity of searching two boundaries is O(n), the total time complexity O(n+nlogn). Some friends may say that we can use count sort and cardinality sort to reduce the sorting time to O(n), but the efficiency is still not high, because in this case, we can not find two boundary subscripts of the original array sort.

We can first from left to right to find the right border, initialize the n = 0, 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, indicated that the position is 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) {const len = array.length const len = array.length If (len < 2) return [-1,-1] let n = 0, Max = array[0], m = len-1, Min = array[len-1] // For (let I = 1; i < len; I ++) {if (array[I] >= Max) Max = array[I] else n = I} i >= 0; I --) {if (array[I] <= min) min = array[I] else m = I} [-1, -1] : [m, n] }Copy the code

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

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻