자바 배열 에서 배열 길이 의 절반 이 넘 는 숫자 를 찾 았 습 니 다.
1742 단어 알고리즘
/**
* ， 。
* 9 {1,2,3,2,2,2,5,4,2}。
* 2 5 ， ， 2。 0。
*/
public int findMoreThanHalfNum(int[] numbers) {
int length = numbers.length;
if (length == 0) return 0;
int num = numbers[0], count = 1;
for (int i = 1; i < length; i++) {
if (numbers[i] == num) count++;
else count--;
if (count == 0) {
num = numbers[i];
count = 1;
}
}
// Verifying
count = 0;
for (int i = 0; i < length; i++) {
if (numbers[i] == num) count++;
}
if (count * 2 > length) return num;
return 0;
}이 알고리즘 은 제 가 생각 하기 시작 한 것 은 hashmap 로 만 드 는 것 입 니 다.숫자 를 key 로 하고 value 는 중복 횟수 입 니 다.마지막 으로 중복 횟수 가 가장 많은 것 을 찾 아 length/2 와 비교 해 보면 만 들 수 있 을 것 입 니 다.하지만 다른 사람의 알고리즘 을 보 니 너무 좋 았 습 니 다.위의 코드 는 사고방식 이 매우 좋아 서'병사 가 진 지 를 공격 하 는 것'과 유사 하 다.우 리 는 수 조 를 한 무리의 병사 라 고 상상 했다.이 병사 들 은 서로 다른 진영 에서 왔 다.병사 들 은 하나씩 병영 을 나 가 진 지 를 공격 했다.첫 번 째 병사 가 진 지 를 점령 한 후에 뒤에 온 병 사 는 자기 사람 일 수도 있 고 자기 사람 이 아 닐 수도 있다.자기 사람 이 라면 count+1.자기 사람 이 아니라면 함께 죽 고 마지막 에 한 사람 이 끝까지 살 것 이다.그러나 이 사람 이 꼭 사람 이 가장 많은 진영 에 속 하 는 것 은 아니다.예 를 들 어'3,3,3,1,2,0',첫 번 째 3 은 먼저 올 라 가 고 두 번 째 3 은 올 라 가 고 세 번 째 3 은 올 라 가 는데 이때 count=3,뒤에 1 은 올 라 가 고 3-1=2,2 는 올 라 가 고 2-1=1 은 올 라 가 고 1-1=0 이다.이때 마지막 에 남 은 것 은 0 이다.그러나 0 은 인원 이 가장 많은 진영 의 병사 가 아니 라 인원 이 가장 많은 진영 이 다른 진영 에 의 해 소모 되 었 다.출전 순서 가'3,1,3,3,2,0'으로 바 뀌 면 마지막 에 남 은 사람 은 3 이지 만 3 개 3 은 없다'(6/2).만약 에 3 의 수량 이 하나 더 많 으 면 아무리 등장 해도 마지막 에 남 은 것 은 3 이다.사람 이 많 기 때문에 절반 과 함께 죽 으 면 항상 하인 이 남는다.이때 4 개의 3>(7/2)이 분명 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
