-
Notifications
You must be signed in to change notification settings - Fork 0
/
Maximum Product of Three Numbers
158 lines (147 loc) · 4.71 KB
/
Maximum Product of Three Numbers
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
/*
LeetCode 628:
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
Note:
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
Solution:
Language: C++
Tag: sort
*/
class Solution {
public:
#define max(a, b) (a > b ? a : b)
int maximumProduct(vector<int>& nums) {
/*
// 1. brute force -- O(n^3) time + O(1) space -- Time Limit Exceed
int res = INT_MIN, size = nums.size();
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < size; ++j) {
for (int k = j + 1; k < size; ++k) {
int tmp = nums[i] * nums[j] * nums[k];
res = max(res, tmp);
}
}
}
return res;
*/
if (nums.size() < 3) {
return 0;
}
/*
// 2. O(nlogn) time + O(1) space
int size = nums.size();
sort(nums.begin(), nums.end(), greater<int>());
//quicksort(nums, 0, size - 1);
//heapsort(nums);
//int *temp = new int[size];
//mergesort(nums, 0, size - 1, temp);
int tmp1 = nums[0] * nums[1] * nums[2]; // all neg or all pos
int tmp2 = nums[0] * nums[size - 1] * nums[size - 2];
return max(tmp1, tmp2);
*/
// 3. O(n) time + O(1) space ???? -- find max1, max2, max3 && min1, min2
int min1 = INT_MAX, min2 = INT_MAX;
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] < min1) {
min2 = min1;
min1 = nums[i];
} else if (nums[i] < min2) {
min2 = nums[i];
}
if (nums[i] > max1) {
max3 = max2;
max2 = max1;
max1 = nums[i];
} else if (nums[i] > max2) {
max3 = max2;
max2 = nums[i];
} else if (nums[i] > max3) {
max3 = nums[i];
}
}
return max(max1 * min1 * min2, max1 * max2 * max3);
}
void quicksort(vector<int> &nums, int start, int end) {
if (start >= end) {
return;
}
int left = start, right = end, pivot = nums[(start + end) / 2];
while (left <= right) {
while (left <= right && nums[left] > pivot) {
++left;
}
while (left <= right && nums[right] < pivot) {
--right;
}
if (left <= right) {
swap(nums[left++], nums[right--]);
}
}
quicksort(nums, start, right);
quicksort(nums, left, end);
}
void mergesort(vector<int> &nums, int start, int end, int *temp) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergesort(nums, start, mid, temp);
mergesort(nums, mid + 1, end, temp);
merge(nums, start, end, temp);
}
void merge(vector<int> &nums, int start, int end, int *temp) {
int mid = start + (end - start) / 2;
int left = start, right = mid + 1, idx = start;
while (left <= mid && right <= end) {
if (nums[left] >= nums[right]) {
temp[idx++] = nums[left++];
} else {
temp[idx++] = nums[right++];
}
}
while (left <= mid) {
temp[idx++] = nums[left++];
}
while (right <= end) {
temp[idx++] = nums[right++];
}
for (int i = start; i <= end; ++i) {
nums[i] = temp[i];
}
}
void heapsort(vector<int> &nums) {
int size = nums.size();
for (int i = (size - 1) / 2; i >= 0; --i) {
siftdown(nums, i, size);
}
while (size > 0) {
swap(nums[0], nums[--size]);
siftdown(nums, 0, size);
}
}
void siftdown(vector<int> &nums, int father, int size) {
while (father < size) {
int min_idx = father;
int left = father * 2 + 1, right = father * 2 + 2;
if (left < size && nums[left] < nums[min_idx]) {
min_idx = left;
}
if (right < size && nums[right] < nums[min_idx]) {
min_idx = right;
}
if (father == min_idx) {
break;
}
swap(nums[father], nums[min_idx]);
father = min_idx;
}
}
};