수조 의 유일한 최소 증 량 인 수학 사유의 운용
2448 단어 알고리즘
주어진 정수 배열
A 은 move 작업 마다 임 의 A[i] 를 선택 하고 증가 1 합 니 다.반환 사 A 의 모든 값 은 유일한 최소 조작 횟수 입 니 다.입력 예제: [3, 2, 1, 2, 1, 7] 출력 예제: 6 해석: 6 번 의 move 작업 을 거 쳐 배열 은 [3, 4, 1, 2, 5, 7] 로 변 합 니 다.알림: 0 <= A.length <= 40000 0 <= A[i] < 40000C++ int minIncrementForUnique(vector<int>& A)0x 02. 간략 분석
이 문 제 를 보 자마자 좀 어 리 석 었 을 것 이다. 같은 것 이 있 으 면 1 을 더 하면 1 을 더 한 후에 다른 숫자 와 같 을 수도 있 고 계속 더 하면 어느 구석 에 한 개의 숫자 가 중복 되 었 을 수도 있 기 때문에 이런 단순 한 스 캔 배열 은 실행 가능 형 이 크 지 않 아 보인다.
우 리 를 괴 롭 히 는 문 제 는 주로 무엇 입 니까?
바로, 당신 은 다 넣 은 후에 어떤 숫자 가 이 숫자 와 같 을 지 모 릅 니 다. 만약 우리 가 같은 것 을 찾 을 수 있 었 으 면 좋 겠 습 니 다.
그래서 생각 이 났 어 요. 정렬!!
정렬 한 후에 똑 같은 것 은 모두 함께 있 을 것 이다. 만약 에 1 을 더 하면 다음 숫자 에 따라 충돌 여 부 를 판단 할 수 있다. 그러면 이 번 거 로 운 문 제 는 해 결 될 것 이다. 그리고 우 리 는 구체 적 인 사고 방향 을 곰 곰 이 생각해 보 자.
정렬 후
A[i]==A[i-1] 여기 서 중복 되 었 다 는 것 을 설명 하면 가장 쉬 운 방법 은 A[i]+1 이다.만약
A[i]네?왜 이런 상황 이 발생 하 는 것 일 까. 앞 에 똑 같은 조건 에서 앞의 수가 커 질 수 있 기 때문에 이때 가장 좋 은 방법 은 역시 A [i] = A [i - 1] + 1, 조 수 를 위 한 'A [- 1] - [i] + 1 이 다. 왜 가장 좋 은 방법 은 역시 A [i] = A [- i - 1] + 1, 조 수 는 A [- 1] - A] - [i] + 1 이 다. 왜 유 우 리 는 장 운 운 운운운운운운법 인 은 은 은 의 하 나 나 를 이용 하 는 커 뮤 니 케 이 션 으로 인해 유 지 를 유지 하 게 되 었 다 고 라 라 라 는 라 라 라 고 해 해 해 해 해 해 해 해 해 해 해 해 해 해 해 를 받 는 커 커 질 수 있 게 유지 하 라 고 라 라 라 라 라 는 라 라 라 라 고 고 까?한 배열 에 있어 서 모두 중복 되 지 않 는 이상 적 인 조건 은 바로 뒤의 것 이 바로 이전 보다 1 크 고 우리 의 목적 은 바로 이 이상 적 인 조건 을 창조 하 는 것 이기 때문이다.주의: 사실 소스 배열 의 수 치 는 계속 바 뀌 고 있 습 니 다. 그러면 우 리 는 중복 되 지 않 을 것 이 라 고 보장 할 수 있 습 니 다. 쉽게 정렬 하지 마 세 요. 정렬 의 목적 은 순 서 를 배열 한 후에 문 제 를 더욱 편리 하 게 해결 할 수 있 습 니 다. 그렇지 않 으 면 오히려 시간 낭 비 를 초래 할 수 있 습 니 다. 기본 값 은 오름차 순 이 고 C + + 바 텀 은 정렬 과 빠 른 정렬 을 삽입 하여 사용 합 니 다. 0x 03. 해결 코드 – 정렬 후 해결class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int ans=0;
sort(A.begin(),A.end());
for(int i=1;i<A.size();i++){
if(A[i]<=A[i-1]){
ans+=A[i-1]-A[i]+1;
A[i]=A[i-1]+1;
}
}
return ans;
}
};
ATFWUS --Writing By 2020–03–22
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
