이미 정렬 된 두 배열 의 중위 수 를 찾 아 라.
1461 단어 알고리즘(Algorithm)
두 배열 의 배열 을 주 고, 한 길 이 는 m (m > = 1) 이 며, 한 길 이 는 n (n > = 1) 이 며, 이 두 배열 의 중위 수 를 찾 아 라.시간 복잡 도 는 O (m + n) 이 고 공간 복잡 도 는 O (1) 이다.
사실 이 문제 자 체 는 어렵 지 않 고 관건 적 인 관건 은 일부 경계 조건 에 대한 처리 이다.
생각:
우 리 는 우선 두 배열 에 몇 개의 숫자 가 포함 되 어 있 든 지 간 에 먼저 제 (m + n + 1) / 2 개의 숫자의 값 을 얻는다.만약 m + n 이 홀수 라면, 우 리 는 제 로 돌아 갑 니 다. (m + n + 1) / 2, m + n 이 짝수 라면 (m + n + 2) / 2 번 째 숫자 를 찾 아 평균 을 구한다.
public class Med {
public static float getMedian(int[] a, int[] b) {
if (a == null || b == null || (a.length + b.length) == 0) return Float.MIN_VALUE;
int pa = 0;
int pb = 0;
float median = 0;
while (pa + pb != (a.length + b.length + 1) / 2) {
int Ai = (pa == a.length) ? Integer.MAX_VALUE : a[pa];
int Bj = (pb == b.length) ? Integer.MAX_VALUE : b[pb];
if (Ai < Bj) {
median = a[pa];
pa++;
} else {
median = b[pb];
pb++;
}
}
if ((a.length + b.length) % 2 == 1) {
return median;
} else {
int Ai = (pa == a.length) ? Integer.MAX_VALUE : a[pa];
int Bj = (pb == b.length) ? Integer.MAX_VALUE : b[pb];
int median2 = (Ai < Bj) ? Ai : Bj;
return (float)(median + median2) / 2;
}
}
public static void main(String[] args) {
int[] b = {1, 2};
int[] a = {5, 6};
System.out.println(getMedian(a,b));
}
}전재 출처 를 밝 혀 주 십시오:http://blog.csdn.net/beiyeqingteng
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
