-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathCode_12_SmallSum.java
More file actions
162 lines (149 loc) · 4.28 KB
/
Code_12_SmallSum.java
File metadata and controls
162 lines (149 loc) · 4.28 KB
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
154
155
156
157
158
159
160
161
162
package algorithm.basic;
/**
* @Created by mood321
* @Date 2019/9/30
* @Description 小和问题
* 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
* 例子：
* [1,3,4,2,5]
* 1左边比1小的数，没有；
* 3左边比3小的数，1；
* 4左边比4小的数，1、3；
* 2左边比2小的数，1；
* 5左边比5小的数，1、3、4、2；
* 所以小和为1+1+3+1+1+3+4+2=16
*/
public class Code_12_SmallSum {
// for test
public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (smallSum(arr1) != comparator(arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
/**
* 出入一个数组 获取数组的小和
* @param arr
* @return
*/
private static int smallSum(int[] arr) {
if(arr==null|| arr.length<2 ){
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
/**
* 用分治的思想 拆分数组 求出每个小数组的小和 然后合并
* @param arr
* @param i
* @param i1
* @return
*/
private static int mergeSort(int[] arr, int L, int R) {
if(L==R){
return 0;
}
int mid=L+((R-L)>>1);
return mergeSort(arr,L,mid)+mergeSort(arr,mid+1,R)+merge(arr, L, mid, R);
}
/**
* merge方法用来合并 分治下来的两个数组的小和
* @param arr
* @param l
* @param mid
* @param r
* @return
*/
private static int merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
int res = 0;
while (p1 <= m && p2 <= r) {
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
}