JZ-C-36

剑指offer第三十六题:数组中的逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//============================================================================
// Name        : JZ-C-36.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 数组中的逆序对
//============================================================================
 
#include <iostream>
#include <stdio.h>
using namespace std;
 
int InversePairsCore(int* data, int* copy, int start, int end);
 
/**
 *统计逆序对的过程:先把数组分隔成子数组,1:先统计出子数组内部的逆序对的数目,
 *2:然后再统计出两个相邻子数组之间的逆序对数目。★在统计逆序对的过程中,还需要对数组进行排序(归并排序)
 */
int InversePairs(int* data, int length) {
    if (data == NULL || length < 0)
        return 0;
 
    int* copy = new int[length];
    for (int i = 0; i < length; ++i)
        copy[i] = data[i];
 
    int count = InversePairsCore(data, copy, 0, length - 1);
    delete[] copy;
 
    return count;
}
/**
 *类似归并排序,每次递归拆分为两个子数组,缩小为两个单元素时候比较大小获得count逆序对数,最后再缩小为同一个元素时候返回。
 */
int InversePairsCore(int* data, int* copy, int start, int end) {
    if (start == end) {
        copy[start] = data[start];
        return 0; //最后缩小为同一个元素,直接返回
    }
 
    int length = (end - start) / 2;
 
    int left = InversePairsCore(copy, data, start, start + length); //注意此处参数:copy,data,交换的原因在于需要对子数组进行排序(归并)。
    int right = InversePairsCore(copy, data, start + length + 1, end);
 
    // i初始化为前半段最后一个数字的下标
    int i = start + length;
    // j初始化为后半段最后一个数字的下标
    int j = end;
    int indexCopy = end;
    int count = 0; //count为被拆两个子数组相比较得出的逆序对数
    while (i >= start && j >= start + length + 1) {
        if (data[i] > data[j]) {
            copy[indexCopy--] = data[i--];
            count += j - start - length;
        } else {
            copy[indexCopy--] = data[j--];
        }
    }
 
    for (; i >= start; --i)
        copy[indexCopy--] = data[i];
 
    for (; j >= start + length + 1; --j)
        copy[indexCopy--] = data[j];
 
    return left + right + count;
}
 
// ====================测试代码====================
void Test(char* testName, int* data, int length, int expected) {
    if (testName != NULL)
        printf("%s begins: ", testName);
 
    if (InversePairs(data, length) == expected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}
 
void Test1() {
    int data[] = { 1, 2, 3, 4, 7, 6, 5 };
    int expected = 3;
 
    Test("Test1", data, sizeof(data) / sizeof(int), expected);
}
 
// 递减排序数组
void Test2() {
    int data[] = { 6, 5, 4, 3, 2, 1 };
    int expected = 15;
 
    Test("Test2", data, sizeof(data) / sizeof(int), expected);
}
 
// 递增排序数组
void Test3() {
    int data[] = { 1, 2, 3, 4, 5, 6 };
    int expected = 0;
 
    Test("Test3", data, sizeof(data) / sizeof(int), expected);
}
 
// 数组中只有一个数字
void Test4() {
    int data[] = { 1 };
    int expected = 0;
 
    Test("Test4", data, sizeof(data) / sizeof(int), expected);
}
 
// 数组中只有两个数字,递增排序
void Test5() {
    int data[] = { 1, 2 };
    int expected = 0;
 
    Test("Test5", data, sizeof(data) / sizeof(int), expected);
}
 
// 数组中只有两个数字,递减排序
void Test6() {
    int data[] = { 2, 1 };
    int expected = 1;
 
    Test("Test6", data, sizeof(data) / sizeof(int), expected);
}
 
// 数组中有相等的数字
void Test7() {
    int data[] = { 1, 2, 1, 2, 1 };
    int expected = 3;
 
    Test("Test7", data, sizeof(data) / sizeof(int), expected);
}
 
void Test8() {
    int expected = 0;
 
    Test("Test8", NULL, 0, expected);
}
 
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
    Test8();
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注