LeetCode 면접 문제 16.16 부분 정렬
8503 단어 알고리즘 문제 풀이알고리즘leetcode정렬 알고리즘
원제 링크
https://leetcode-cn.com/problems/sub-sort-lcci/
제목 설명
정수 배열 을 지정 하고 함 수 를 작성 하여 색인 m 와 n 을 찾 습 니 다. 색인 구간 [m, n] 의 요 소 를 정렬 하면 전체 배열 이 질서 가 있 습 니 다.주의: n - m 는 가능 한 한 최소 화 합 니 다. 즉, 조건 에 맞 는 최 단 서열 을 찾 는 것 입 니 다.함수 반환 값 은 [m, n] 입 니 다. 이러한 m 와 n 이 존재 하지 않 는 다 면 [- 1, - 1] 을 되 돌려 주 십시오.
예시
예시 1
입력: [1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19] 출력: [3, 9]
2. 알고리즘
방법 1 직접 정렬
사고의 방향
배열 을 정렬 하여 원본 배열 과 비교 합 니 다.
알고리즘
코드
class Solution:
def subSort(self, array):
result = [-1, -1]
sorted_array = sorted(array)
n = len(array)
for i in range(n):
if sorted_array[i] != array[i]:
result[0] = i
break
for j in range(n - 1, -1, -1):
if sorted_array[j] != array[j]:
result[1] = j
break
return result
복잡 도
사고의 방향
만약 에 왼쪽 의 최대 치가 중간의 최소 치보다 크 면 반드시 중간 서열 에 포 함 될 것 이다.마찬가지 로 오른쪽 최소 치가 중간의 최대 치보다 크 면 반드시 중간 서열 에 포 함 될 것 이다.
알고리즘
class Solution:
def subSort(self, array):
n = len(array)
if n == 0:
return [-1, -1]
l, r = -1, -1
max_val, min_val = array[0], array[-1]
for i in range(n):
if array[i] >= max_val:
max_val = array[i]
else:
r = i
for j in range(n - 1, -1, -1):
if array[j] <= min_val:
min_val = array[j]
else:
l = j
return [l, r]
복잡 도
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vva1025- 알고리즘 입문 경전제목 링크https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3466분석이 dp[T][n]에서 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
