고도 검사 표 - 알고리즘 필기 총화
고도 검사 표:
학 교 는 연도 기념 사진 을 찍 을 때 일반적으로 학생 들 에 게 비 체감 의 높이 순서에 따라 배열 하도록 요구한다.모든 학생 들 이 비 체감 고도 로 배열 할 수 있 는 최소 이동 인원 을 되 돌려 주 십시오.
한 조 의 학생 이 선택 되 었 을 때, 그들 사 이 는 가능 한 한 정렬 을 다시 할 수 있 으 며, 선택 되 지 않 은 학생 들 은 움 직 이지 않 아야 합 니 다.
예시:
：heights = [1,1,4,2,1,3]
：3
설명: 현재 배열: [1, 1, 4, 2, 1, 3] 목표 배열: [1, 1, 1, 2, 3, 4] 아래 표 시 된 2 곳 (0 부터 계산) 에 4 vs 1 이 나타 나 기 때문에 우 리 는 이 학생 을 이동 해 야 한다.아래 표 시 된 4 곳 (0 부터 계산) 에 1 vs 3 이 나타 나 기 때문에 우 리 는 이 학생 을 이동 해 야 한다.아래 표 시 된 5 곳 (0 부터 계산) 에 3 vs 4 가 나타 나 기 때문에 우 리 는 이 학생 을 이동 해 야 한다.
예시 2:
：heights = [5,1,2,3,4]
：5
예시 3:
：heights = [1,2,3,4,5]
：0
알림:
1 <= heights.length <= 100 1 <= heights[i] <= 100
테스트 용례
[2] [1,2,3,4,5] [5,4,3,2,1] [5,1,2,3,4] [1,1,4,2,1,3] [3,3,4,3,4,3]
사고 분석.
해법 1: 정렬 비교
사고: 먼저 원 배열 을 복제 하고 복 제 된 배열 을 정렬 한 다음 에 순서대로 가격 비교 배열 과 원 배열 이 각 위치 에서 똑 같은 지 분석 합 니 다. 사고 가 비교적 간단 하고 시간 복잡 도 는 O (nlogn) 공간 복잡 도 는 O (n) 입 니 다.
해법 2: 통 정렬 구 해
사고: 우 리 는 제 시 된 요소 가 두 가지 조건 을 만족 시 키 고 길이 가 100 보다 낮 으 며 수 치 는 1 - 00 사이 에 있다 는 것 을 알 게 되 었 다. 그러면 정렬 하 는 과정 은 이 특징 에 따라 최적화 할 수 있 고 101 길이 의 배열 을 구축 할 수 있다. 통 정렬 으로 분석 할 수 있다. 시간 복 잡 도 는 파 용 통 으로 정렬 되 기 때문에 복잡 도 는 O (n) 이 고 101 길이 의 보조 공간 은 상수 급 이다.공간 복잡 도 O (1)
import java.util.Arrays;
/**
@author cosefy
@date 2020/6/25
*/
public class HeightChecker {
public static void main(String[] args) {
int[] nums = {1,1,4,2,1,3};
int res1 = test1(nums);
System.out.println(" ： " + res1);
int res2 = test2(nums);
System.out.println(" ： " + res2);
}
// ：
public static int test1(int[] nums) {
int[] sortedArr = nums.clone();
Arrays.sort(sortedArr);
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != sortedArr[i])
++count;
}
return count;
}
// ：
public static int test2(int[] nums) {
int[] arr = new int[101];
for (int num : nums) {
++arr[num];
}
int count = 0;
for (int i = 0, j = 0; i < arr.length; i++) {
while (arr[i] > 0) {
if (nums[j++] != i)
++count;
--arr[i];
}
}
return count;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
