Java에서 비내림 배열을 구현하는 방법

문제 설명

n개의 정수가 포함된 배열이 있는 경우 최대 하나의 요소를 수정하여 배열이 내림차순이 될 수 있는지 확인하는 것이 작업입니다. 비내림차순 배열은 모든 i(1

샘플 1:

ⅰ 입력: [4,2,3]

ⅱ 출력: True

ⅲ 참고: 첫 번째 숫자 4를 1로 변경하여 [1,2,3]을 얻을 수 있습니다. 비내림차순 배열

샘플 2:

ⅰ 입력: [4,2,1]

ⅱ 출력: False

ⅲ 설명: 최대 하나의 요소를 수정하여 배열을 비내림차순으로 만들 수 없습니다.

문제 해결 아이디어 분석

a. 단순히 생각하면 조건을 수정하지 않고 충족하는 상황, 요소 하나만 수정하여 조건을 충족할 수 있는 상황, 그리고 조건부로 하나의 요소를 수정해도 만족할 수 없는 것입니다. 첫 번째 경우에는 배열을 탐색하여 배열의 각 항목이 이전 항목보다 크거나 같은지 확인합니다. 그렇다면 true를 반환합니다. 두 번째 경우에는 수정하려는 배열[i]의 수를 열거한 후, 배열[i] 앞의 숫자가 감소하지 않는지, 배열[i] 뒤의 숫자가 감소하지 않는지 확인하면 마지막으로 , array[i-1]이 true인지 확인해야 합니다(array[i]가 경계에 있는지 확인할 필요가 없음). true인 경우 배열을 변경할 수 있습니다. [i]에서 array[i -1]과 array[i+1] 사이의 임의의 숫자는 배열을 비내림차순 배열로 만들고 모든 i에 대해 true가 아닌 경우 true가 반환됩니다. 3이고 false가 반환됩니다. 이를 수행하는 데 드는 시간 복잡도는 O(n^2)이고 추가 공간 복잡도는 O(1)입니다.

b. 숫자를 수정한 후 비내림차순 배열로 변경하려면 어떤 조건이 충족되나요? 분명히, 그러한 배열은 비거절 조건을 만족하지 않는 인접한 숫자 쌍이 하나만 있다는 조건을 만족해야 합니다. 즉, array[i를 만족하는 고유한 i(1array[i], 이러한 i가 여러 개인 경우 최대 하나의 숫자를 수정하여 원래 배열이 비내림차순 배열이 될 수 없다고 주장할 수 있습니다. 그러면 이 조건을 충족하는 배열은 숫자를 수정하여 비거절을 충족할 수 있습니까? 아니요, 예를 들어 [2,4,1,3]의 경우 인접한 4,1만이 비감소를 만족하지 못하지만, 숫자 하나만 변경한다고 해서 비감소가 될 수는 없습니다. 실제로 array[i-1]>array[i]를 만족하는 i가 하나만 있는 경우 수정하려는 숫자는 array[i-1]과 array[i] 두 숫자 중 하나여야 합니다. 이전 접근 방식을 적용하고 두 상황에 대해 별도의 판단을 내릴 수 있습니다. 더욱이 array[i-1]>array[i]는 i에 대해서만 참이므로, 다른 인접한 숫자는 모두 비감소 조건을 만족하므로 array[i-1]에 대해서는 그 앞과 뒤의 배열이 같다고 한다. 각각 비내림차순 조건을 만족하고, array[i]도 마찬가지이므로 앞과 뒤의 두 배열을 비내림차순 배열로 연결할 수 있는지 여부만 판단하면 됩니다. 구체적으로 수정하려는 숫자가 array[i-1]인 경우 array[i-2]array[i]이고, 최종적으로 true를 반환하는 조건은 array[i-1], array[i]가 경계, 또는 배열[i-2]

참조 프로그램

Java 버전:

위 내용은 Java에서 비내림 배열을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!