資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究在C++中查詢陣列中滿足x^y > y^x的(x, y)對的數量
假設我們有兩個正整數陣列X和Y。找出滿足x^y > y^x的(x, y)對的數量，其中x是X的元素，y是Y的元素。例如，如果X = [2, 1, 6]，Y = [1, 5]，則輸出為3。因為存在三對：(2, 1), (2, 5) 和 (6, 1)
我們可以用一種高效的方法解決這個問題。邏輯很簡單，當y > x時，x^y > y^x，但有一些例外情況。這就是技巧所在。
對陣列Y進行排序
對於X中的每個元素x，我們必須在Y中找到大於x的最小數字的索引。我們將使用二分查詢來實現。或者我們也可以使用upper_bound()函式。
找到的索引之後的所有數字都滿足關係，因此只需將它們新增到計數中。
示例
#include <iostream>
#include <algorithm>
using namespace std;
int count(int x, int Y[], int n, int no_of_y[]) {
if (x == 0)
return 0;
if (x == 1)
return no_of_y[0];
int* index = upper_bound(Y, Y + n, x);
int ans = (Y + n) - index;
ans += (no_of_y[0] + no_of_y[1]);
if (x == 2)
ans -= (no_of_y[3] + no_of_y[4]);
if (x == 3)
ans += no_of_y[2];
return ans;
}
int howManyPairs(int X[], int Y[], int m, int n) {
int no_of_y[5] = {0};
for (int i = 0; i < n; i++)
if (Y[i] < 5)
no_of_y[Y[i]]++;
sort(Y, Y + n);
int total_pairs = 0;
for (int i=0; i< m; i++)
total_pairs += count(X[i], Y, n, no_of_y);
return total_pairs;
}
int main() {
int X[] = {2, 1, 6};
int Y[] = {1, 5};
int m = sizeof(X)/sizeof(X[0]);
int n = sizeof(Y)/sizeof(Y[0]);
cout << "Total pair count: " << howManyPairs(X, Y, m, n);
}輸出
Total pair count: 3
更新於：2020年1月3日
208 次瀏覽
廣告