【原】劍指offer之?dāng)?shù)組中的逆序?qū)?/span>

陳喻 2021-10-19

展開全文

1 問(wèn)題

在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對(duì)1000000007取模的結(jié)果輸出。即輸出P%1000000007。

比如數(shù)列{6，202，100，301，38，8，1}，有14個(gè)序列對(duì)；

比如數(shù)列{7, 5, 6, 4}，有5個(gè)序列對(duì){7,5}，{7,6}，{7,4}，{5,4}，{6,4}；

2 分析

我們先了解下歸并排序，前面博客有介紹??劍指offer之歸并排序?，我們分析數(shù)列{6，202，100，301，38，8，1}，

第一次歸并后：{6,202},{100,301},{8,38},{1}，這里逆序?qū)?對(duì)，就是我們把8插入了38前面，后面只有38一個(gè)數(shù)據(jù)，所以是一度

第二次歸并后：{6,100,202,301}，{1,8,38}，這里逆序?qū)τ?對(duì)，我們把100插入了數(shù)組{6,202}之間，后面只有202一個(gè)元素，所以有一對(duì)逆序?qū)?#xff0c;然后1插入了數(shù)組{8， 38}最前面，這里后面還有2個(gè)元素，所以這有2個(gè)逆序?qū)Α?/p>

第三次歸并后：{1,6,8,38,100,202,301},這里逆序?qū)τ?0對(duì)，把1出入了數(shù)組{6,100,202,301}最前面，后面有4個(gè)數(shù)據(jù)，所以4對(duì)，然后把8插入數(shù)組{6,100,202,301}的第二個(gè)數(shù)據(jù)，后面還有3個(gè)數(shù)據(jù)，就是3對(duì)，然后再把38插入數(shù)組{6,100,202,301}里面，后面還有3個(gè)數(shù)據(jù)，也就是還有3對(duì)逆序?qū)?/p>

規(guī)律：我們把右邊數(shù)組里面的元素插入左邊數(shù)組元素的時(shí)候，插進(jìn)去的位置后面到左邊數(shù)組尾巴多有多少個(gè)元素，就有多少個(gè)逆序?qū)?#xff0c;每插入依次，我們統(tǒng)計(jì)一次，依次累加。

?

3 代碼實(shí)現(xiàn)

#include <stdio.h>

int lastResult = 0;

void merge(int* source, int* temp, int start, int mid, int end)
{
    if (source == NULL || temp == NULL)
    {
        printf("merge source or temp is NULL\n");
        return;
    }
    int i = start, j = mid + 1, k = start;
    int count = 0;
    while (i != mid + 1 && j != end + 1)
    {
        if (source[i] > source[j])
        {
            temp[k++] = source[j++];
            count = mid - i + 1;
            lastResult += count;
        }
        else
            temp[k++] = source[i++];
    }
    while (i != mid + 1)
        temp[k++] = source[i++];
    while (j != end + 1)
        temp[k++] = source[j++];
    for(int h = start; h <= end; ++h)
    {
        source[h] = temp[h];   
    }
    return;
}

int static result = 0;
 
void mergeSort(int* source, int* temp, int start, int end)
{
    if (source == NULL || temp == NULL)
    {
        printf("mergeSort source or temp is NULL\n");
        return;
    }
    
    if (start < end)
    {
        int mid = start + (end - start) / 2;
        mergeSort(source, temp, start, mid);
        mergeSort(source, temp, mid + 1, end);
        merge(source, temp, start, mid, end);
    }
}

void printDatas(int* datas, int len)
{
    for (int i = 0; i < len; ++i)
    {
        printf("%d\t", datas[i]);
    }
    printf("\n");
}


int main(void) { 
    int source[] = {7, 5, 6, 4};
    int temp[4];
    int length =  sizeof(source) / sizeof(int);
    mergeSort(source, temp, 0, length - 1);
    printf("lastResult is %d\n", lastResult % 1000000007);
    return 0;
}