자바 인터뷰에서 병합 정렬 적용

글의 배경:

알고리즘과 자료구조를 복습하다가 시험문제로 작성된 인터뷰를 발견했습니다. 문제를 살펴보겠습니다:

(학습 영상 공유: java 교육 영상)

In 두 숫자의 배열, 이전 숫자가 다음 숫자보다 크면 두 숫자는 역순 쌍을 형성합니다. 배열을 입력하고 배열에 포함된 역순 쌍 P의 총 개수를 찾습니다. 그리고 P 모듈로 1000000007의 결과를 출력합니다. 즉, 출력 P%1000000007

입력 설명:

질문은 입력 배열에 동일한 숫자가 없음을 확인합니다

데이터 범위:

%50 데이터의 경우 크기<=10^4

%75의 경우 data, size<=10^5

For %100 data, size<=2*10^5

분석:

이 질문은 직접 풀기 쉽지만 시간 복잡도는 o(n*n)입니다. 이 질문을 받았을 때 아무 생각 없이 dp로 직접 작성했는데, dp가 직접 해결하는 것만큼 좋지 않다는 것을 알았습니다. dp도 2*10을 차지합니다. ^5 공백. 다음은 직접적입니다. 메소드와 dp가 모두 시간 초과되었습니다.

(더 관련 있는 면접 질문 추천: java 면접 질문 및 답변)

코드 공유:

  //直接求法 ,超时
public  class solution{
   public static  int sum;
   
   public static int InversePairs(int [] array) {
        dp(array);
        return sum;
   }
   
 
   public static void dp(int []array){
       for(int i = array.length - 1 ; i >  0 ; i --){
           for(int j = i - 1 ; j >= 0 ; j--){
                if(array[j] > array[i]){
                	sum += 1;
                } 
           }
           sum %= 1000000007;
       }
       
   }
}

public  class solution{
 
  //一维数组dp   
   public static  int sum;
   
   public static int InversePairs(int [] array) {
        dp(array);
        return sum;
   }
   public static int count[] = new int[200004];
   
   public static void dp(int []array){
       for(int i = array.length - 1 ; i >  0 ; i --){
           for(int j = i - 1 ; j >= 0 ; j--){
                if(array[j] > array[i]){
                	count[j] = count[j+1]+1;
                }else {
                	count[j] = count[j+1];
                }
           }
           sum += count[0];
           sum %= 1000000007;
           for(int k = 0 ; k < array.length ; k ++)
        	   count[k] = 0;
       }
       
   }
    
}

dp는 여기서 중복됩니다.

다음은 병합 정렬을 이해하지 못하는 경우, 나를 볼 수 있습니다. 이전 블로그 Merge sort:

public class solution{   
    //归并排序AC
    public static int  cnt ;
    
    public static  int InversePairs(int [] array) {
         
        if(array != null){
             RecusionSorted(array,0,array.length - 1);
        }
        return  cnt%1000000007;
    }	
	
	public static void MegerArray(int[] data, int start, int mid, int end) {
		 int temp[] = new int[end-start+1]; 
		 int i  =  mid;
		 int j = end;
		 int m = mid+1;
		 int z = 0;
		 while(j >= m && i >= start) {
			 if(data[i] > data[j]) {
				 temp[z++] = data[i--];
				 cnt += (j-mid)%1000000007;
                 cnt %= 1000000007;
			 }else {
				 temp[z++] = data[j--];
			 }
		 }
		 
		 while(j >= m) {
			 temp[z++] = data[j--];
		 }
		
		 while(i >= start) {
			 temp[z++] = data[i--];
		 }
		 
		 for(int k = start ; k <= end ; k ++) {
			 data[k] = temp[end - k];
		 }
	}
	
	public static void RecusionSorted(int data[] , int start , int end ) {
		
		
		if(start < end) {
			int mid = (start + end) >> 1;
			RecusionSorted(data,start,mid);
			RecusionSorted(data,mid+1,end);
		    MegerArray(data,start,mid,end);
		} 
	}
}

관련 권장 사항: Java 입문 튜토리얼

위 내용은 자바 인터뷰에서 병합 정렬 적용의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!