How to implement non-descending array in java

Problem description

Given an array containing n integers, your task is to check whether it can become non-descendant by modifying at most one element. A non-descending array satisfies array[i-1]

Sample 1:

ⅰ Input: [4,2,3]

ⅱ Output: True

ⅲ Description : You can change the first number 4 to 1, and get [1,2,3] as a non-descending array

Sample 2:

ⅰ Input: [4,2,1]

ⅱ Output: False

ⅲ Description: The array cannot be made non-descending by modifying at most one element.

Analysis of problem-solving ideas

a. Simple thinking can lead to three situations: No need Modification can satisfy the condition, modification of an element can satisfy the condition, and modification of an element cannot satisfy the condition. For the first case, just traverse the array to see if each item in the array is greater than or equal to the previous item. If so, return true. For the second case, you can enumerate the number array[i] to be modified, and then check whether the number before array[i] is non-decreasing, and whether the number after array[i] is non-decreasing, Finally You should also check whether array[i-1] is true (no need to check if array[i] is at the boundary), if true then You can change array[i] to any number between array[i-1] and array[i 1] to make the array a non-descending array. This is case 2 and returns true. If it is not true for all i, then For case three, return false. The time complexity of doing this is O(n^2), and the additional space complexity is O(1).

b. What conditions can be met to change a number into a non-decreasing array after modifying it? Obviously, such an array should satisfy the condition that there is only one pair of adjacent numbers that does not satisfy the non-decline condition, that is, there is only one unique i (1array[i], It can be asserted that if there are multiple such i's, the original array cannot become a non-descending array by modifying at most one number. So can any array that meets this condition satisfy non-decline by modifying a number? No, for example [2,4,1,3], only the adjacent 4,1 does not satisfy non-decreasing, but it cannot become non-decreasing by changing only one number. In fact, if there is only one i that satisfies array[i-1]>array[i], then the number to be modified must be among the two numbers array[i-1] and array[i], then You can apply the previous approach and make separate judgments on the two situations. Furthermore, since array[i-1]>array[i] is true only for i, all other adjacent numbers satisfy the non-decreasing condition, so for array[i-1] It is said that the arrays before and after it meet the non-descending conditions respectively, and the same is true for array[i]. Therefore, you only need to judge whether the two arrays before and after can be connected into a non-descending array. Specifically, if the number to be modified is array[i-1], then you only need to judge whether array[i-2]array[i], and the conditions for finally returning true are array[i-1], array[i] is the boundary, or array[i-2]

Reference program

Java version:

The above is the detailed content of How to implement non-descending array in java. For more information, please follow other related articles on the PHP Chinese website!