[컴퓨터 노트]자바 가 배열 에서 중복 되 는 숫자 를 찾 아 라.
5220 단어 Java
제목 설명
길이 가 n 인 배열 의 모든 숫자 는 0 에서 n-1 의 범위 안에 있다.배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 는 지 모 르 고 모든 숫자 가 몇 번 반복 되 는 지 모른다.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
문제 풀이 의 사고 방향.
시간 복잡 도 O(N),공간 복잡 도 O(1)를 요구한다.따라서 정렬 방법 을 사용 할 수도 없고,추가 표기 그룹 을 사용 할 수도 없다.
이러한 배열 요소 가[0,n-1]범위 내 에 있 는 문제 에 대해 값 이 i 인 요 소 를 i 번 째 위치 로 조정 하여 해결 할 수 있다.이 문 제 는 중복 되 는 숫자 를 찾 아야 하기 때문에 조정 과정 에서 i 위치 에 i 값 이 있 는 요소 가 있 으 면 i 값 이 중복 되 는 것 을 알 수 있다.
(2,3,1,0,2,5)의 경우 위치 4 에 옮 겨 다 닐 때 이 위치 에 있 는 수 는 2 이지 만 두 번 째 위치 에 2 의 값 이 있 기 때문에 2 중복 을 알 수 있다.
public boolean duplicate(int[] nums, int length, int[] duplication) {
if (nums == null || length <= 0)
return false;
for (int i = 0; i < length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
duplication[0] = nums[i];
return true;
}
swap(nums, i, nums[i]);
}
}
return false;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
