网易互联网笔试8.20

• 给定一个长度为n的正整数数组vec，求符合以下要求的三元组数量：
  且 $vec[i]=vec[k]>vec[j]vec[i]=vec[k]>vec[j]$

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<ctime>

#define MAX 1000000
#define LOWBIT(x) (x&(-x))
#define C2(x) ((x-1)*x/2)

using namespace std;

int tree[MAX];

int solution1(vector<int>& vec) {
	int res = 0;
	for (int i = 0; i < vec.size(); ++i) {
		int middle = 0;
		for (int j = i + 1; j < vec.size(); ++j) {
			if (vec[j] < vec[i]) middle++;
			if (vec[j] == vec[i]) res += middle;
		}
	}
	return res;
}

/*树状数组典型的应用场景：
* 有一个数组，需要得到每个数之前比这个数小的数的个数，每个数的数值大小的范围是[1, MAX]
* 这个场景下采用树状数组可以把问题的复杂度降低到 MAX log MAX
*/


inline void update(int i, int x) {
	for (int pos = i; pos < MAX; pos += LOWBIT(pos)) {
		tree[pos] += x;
	}
}

inline int query(int n) {
	int ans = 0;
	for (int pos = n; pos; pos -= LOWBIT(pos)) {
		ans += tree[pos];
	}
	return ans;
}

int solution2(vector<int>& vec) {
	vector<int> rec(vec.size(), 0);
	for (int i = 1; i < vec.size(); ++i) {
		update(vec[i - 1], 1);
		rec[i] = query(vec[i]);
	}

	unordered_map<int, vector<int>> M;
	for (int i = 0; i < vec.size(); ++i) {
		int num = vec[i];
		M[num].push_back(i);
	}

	unordered_map<int, vector<int>> MT;
	for (auto entry : M) {
		vector<int>& vec = entry.second;
		if (vec.size() == 1) continue;
		int prev = vec[0];
		for (int i = 1; i < vec.size(); ++i) {
			MT[entry.first].push_back(rec[vec[i]] - rec[prev] - 1);
			prev = vec[i];
		}
	}

	int res = 0;
	for (auto entry : MT) {
		int total = entry.second.size() + 1;
		for (int i = 0; i < entry.second.size(); ++i) {
			int left = i + 1;
			int right = entry.second.size() - i;
			res += (C2(total) - C2(left) - C2(right)) * entry.second[i];
		}
	}
	return res;

}


int main() {
	clock_t start, finish;
	vector<int> vec;
	srand((unsigned) time(NULL));
	for (int i = 0; i < 10000; ++i) vec.push_back(rand()%MAX+1);
	start = clock();
	int s1 = solution1(vec);
	finish = clock();
	cout << "solution1: " << s1 << "   " << "cost: " << finish - start << endl;

	start = clock();
	int s2 = solution2(vec);
	finish = clock();
	cout << "solution2: " << s2 << "   " << "cost: " << finish - start << endl;

}

程序输出：

solution1: 2501345 cost: 36608
solution2: 2501345 cost: 235