数组中的逆序对

难点陈说


数组中的逆序对。在数组中的五个数字,假设前方一个数字高于前面包车型客车数字,则那多少个数字组成二个逆序对。输入二个数组,求出这些数组中的逆序对的总额P。并将P对一千000007取模的结果输出。
即输出P%一千000007解答:武力遍历算法复杂度太大。用归并排序完结,算法复杂度为Owww.5929.com 1

套路

  • www.5929.com,排序难点要时刻想到基本的种种排序算法,并且能够熟稔通晓和灵活运用。
  • 亟待搜索排序后一定的数(如中位数)也许多少个数(如最小 /
    大的K个数)往往用堆排序最优,所以对排序也亟需很好的支配一下

注意点

  • 暂无

目录

  • 调动数组顺序使奇数位于偶数前边(直插的变形,稳固)
  • 数组中的逆序对。数组中的逆序对(归并的变形)
  • 数据流中的中位数(堆排序的变形)
  • 小小的的K个数(堆排序的变形)

调动数组顺序使奇数位于偶数前面

输入贰个整数数组,完结叁个函数来调动该数组中数字的一一,使得全数的奇数位于数组的前半片段,全体的偶数位于位于数组的后半部分,并确定保障奇数和奇数,偶数和偶数之间的龃龉地方不改变。

  • 解题思路:认为跟稳固性没什么关系,稳固排序指是相等的数保障相对地方不改变,跟这一个奇数与奇数、偶数与偶数间的相对地方没什么关系。不使用别的额外数据结构,直接插入变形。时间复杂度
    O(n^2), 空中复杂度O(1)

public void reOrderArray(int [] array) {
    if (array == null || array.length == 0) {
        return;
    }
    for (int i = 1; i < array.length; i++) {
        if (array[i] % 2 == 1) {
            int t = array[i];
            for (int j = i - 1; j >= 0; j--) {
                if (array[j] % 2 == 0) {
                    array[j + 1] = array[j];
                    if (j == 0) {
                        array[j] = t;
                    }
                } else {
                    array[j + 1] = t;
                    break;
                }
            }
        }
    }
}

数组中的逆序对

在数组中的两个数字,假使眼下一个数字超越后边的数字,则那七个数字组合三个逆序对。输入二个数组,求出那一个数组中的逆序对的总和P。并将P对1000000007取模的结果输出。
即输出P%一千000007
输入描述:
难题保险输入的数组中并未有的等同的数字
多少范围:对于%50的多少,size<=10^4, 对于%75的数据,size<=10^5,
对于%100的数量,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7

private int total = 0;

public int InversePairs(int [] array) {
    if (array == null) {
        return 0;
    }
    sort(array, 0, array.length - 1);
    return total;
}

private void sort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

private void merge(int[] arr, int low, int mid, int high) {
    int left = low, right = mid + 1, len = high - low + 1;
    int[] temp = new int[len];
    int k = 0;
    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp[k++] = arr[left++];
        } else {
            // 说明数组左边从left到mid的值都大于right
            // 可组成 mid - left + 1个逆序对
            total += mid - left + 1;
            total %= 1000000007;
            temp[k++] = arr[right++];
        }
    }
    while (left <= mid) {
        temp[k++] = arr[left++];
    }
    while (right <= high) {
        temp[k++] = arr[right++];
    }
    for (int i = 0; i < len; i++) {
        // 注意这里从 low 开始加
        arr[low + i] = temp[i];
    }
}

多少流中的中位数

  • 哪些赢得多个数额流中的中位数?即使从数据流中读出奇数个数值,那么中位数正是怀有数值排序之后位于中等的数值。借使从数据流中读出偶数个数值,那么中位数便是装有数值排序之后中间多个数的平均值。
  • 一旦直接插入动态数组,然后排序的话,要实行n次nlogn的排序,也正是n^2logn等级。而优先级队列,能够实现nlogn等级的时刻复杂度。

private int count = 0;
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private PriorityQueue<Integer> maxHeap = 
    new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

public void Insert(Integer num) {
    if (count % 2 == 0) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
    } else {
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll());
    }
    count++;
}

public Double GetMedian() {
    if (count % 2 == 0) {
        return new Double((minHeap.peek() + maxHeap.peek())) / 2;
    } else {
        return new Double(minHeap.peek());
    }
}

最小的K个数

输入n个整数,搜索里面非常小的K个数。举个例子输入4,5,1,6,2,7,3,8那8个数字,则小小的的4个数字是1,2,3,4,。

  • 听闻堆排序算法,构建最大堆。时间复杂度为 O(nlogk)
  • 若果用高速排序,时间复杂度为 O(nlogn);
  • 设若用冒泡排序,时间复杂度为 O(n * k)

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer> list = new ArrayList<>();
    //检查输入的特殊情况
    if(input == null || input.length <= 0 || input.length < k) {
        return list;
    }
    //构建最大堆
    for(int len = k / 2 - 1; len >= 0; len--) {
        adjustMaxHeapSort(input, len, k-1);
    }
    //从第k个元素开始分别与最大堆的最大值做比较,如果比最大值小,则替换并调整堆。
    //最终堆里的就是最小的K个数。
    int tmp;
    for(int i = k; i < input.length; i++) {
        if(input[i] < input[0]){
            tmp = input[0];
            input[0] = input[i];
            input[i] = tmp;
            adjustMaxHeapSort(input, 0, k-1);
        }
    }
    for(int j = 0; j < k; j++) {
        list.add(input[j]);
    }
    return list;
}

public void adjustMaxHeapSort(int[] input, int pos, int length) {
    int temp, child;
    for(temp = input[pos]; 2 * pos + 1 <= length; pos = child) {
        child = 2 * pos + 1;
        if(child < length && input[child] < input[child + 1]) {
            child++;
        }
        if(input[child] > temp) {
            input[pos] = input[child];
        } else {
            break;
        }
    }
    input[pos] = temp;
}

Leave a Comment.