배열

병합정렬

시간 복잡도가 O(nlogn)인 정렬 알고리즘 중 하나입니다. 여기서 n은 주어진 배열의 길이입니다.

///tc : O(nlogn)
//sc : O(n) for creating intermediate arrays a, b of size of part of subarray which is of size n
class Solution {
    public int[] sortArray(int[] nums) {
         merge(0,nums.length-1,nums);
         return nums;
    }
    public void merge(int start, int end, int arr[]){
        if(end>start){
            int mid = (start+end)/2;
            merge(start,mid,arr);
            merge(mid+1,end,arr);
            sort(start, mid,end, arr);
        }
    }
    public void sort(int start, int mid ,int end, int arr[]){
        int a[] = new int[mid-start+1];
        int b[] = new int[end-mid];
        for(int i = 0;i




<hr>

<p>반전 횟수</p>

<p>배열이 정렬되기 전에 필요한 비교 횟수(배열 arr[]의 인덱스 i, j가 주어지면 <strong>arr[i]> arr[j]</strong>(j> i의 경우)는 이 조건이 충족될 때마다 반전이 1씩 계산됩니다.</p>

<p>참고: <em>동일한 병합 정렬 접근 방식을 사용하여 반전 횟수를 찾을 수 있습니다(병합 정렬 코드는 더 쉽게 읽을 수 있도록 약간 변경되었습니다)</em><br>
</p>

<pre class="brush:php;toolbar:false">class Solution {
    // arr[]: Input Array
    // N : Size of the Array arr[]
    // Function to count inversions in the array.

    static long inversionCount(long arr[], int n) {
        // Your Code Here
       //we can use merge sort
       long temp[]= new long[n];
       return merge(0,n-1,arr,temp);


    }
    public static long merge(int start, int end, long arr[],long[] temp){
        long count = 0;
        if(end>start){
            int mid = (start+end)/2;
            count+=merge(start,mid,arr,temp);
            count+=merge(mid+1,end,arr,temp);
           count+=sort(start, mid,end, arr,temp);
        }
        return count;
    }
    public static long sort(int start, int mid ,int end, long arr[],long [] temp){
        long count = 0;
        int i = start;
        int j = mid+1;
        int k = start;

        while(i arr[j] then all the values after ith index including will be
                // greater that jth index value hence count += mid-i+1
            }
            k++;
        }
        while(i




          

            
  

            
        

위 내용은 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!