动态ip怎么建设网站,wordpress essential ,专业制作教学课件,东软集团交换和#xff1a;
给定两个整数数组#xff0c;请交换一对数值#xff08;每个数组中取一个数值#xff09;#xff0c;使得两个数组所有元素的和相等。
返回一个数组#xff0c;第一个元素是第一个数组中要交换的元素#xff0c;第二个元素是第二个数组中要交换的元…交换和
给定两个整数数组请交换一对数值每个数组中取一个数值使得两个数组所有元素的和相等。
返回一个数组第一个元素是第一个数组中要交换的元素第二个元素是第二个数组中要交换的元素。若有多个答案返回任意一个均可。若无满足条件的数值返回空数组。
示例 输入: array1 [4, 1, 2, 1, 1, 2], array2 [3, 6, 3, 3] 输出: [1, 3] 输入: array1 [1, 2, 3], array2 [4, 5, 6] 输出: [] 解题思路
1.首先先对题目进行理解交换两个数使得两个数组的和相等那么就需要分别把两个数组的和计算出来如果sum1和sum2的差值为偶数才有可能可以找到能够交换的数。如果差值为奇数直接返回空数组。
2.sum1和sum2的差值为偶数时diff(sum1-sum2)/2,存在
sum1-array1[i]array2[j] sum2-array2[j]array1[i]
array1[i]diffarray2[j]
此时可以满足交换之后sum1sum2 方法一排序二分查找法
Code:
class Solution {
public:vectorint findSwapValues(vectorint array1, vectorint array2) {sort(array2.begin(), array2.end());int sum1 0, sum2 0, m array1.size(), n array2.size();for (int num : array1) sum1 num;//计算sum1for (int num : array2) sum2 num;//计算sum2//如果差值为奇数不会存在两个数符合题意if ((sum2 -sum1) % 2) return {}; // 两个数组的差值必须是偶数int diff (sum2 - sum1) / 2; // 需满足 y x diff;for (int i 0;i m; i) {int target array1[i] diff;int left 0, right n - 1, mid;//对数组2进行二分查找法while (left right) {mid (right left) 1;//找到目标元素if (array2[mid] target) {return {array1[i], array2[mid]};}else if (array2[mid] target) right mid - 1;else left mid 1;}}return {}; // 没有找到符合题意的两个数}
}; 方法二排序双指针
class Solution {
public:vectorint findSwapValues(vectorint array1, vectorint array2) {sort(array1.begin(), array1.end()); // 对array1排序sort(array2.begin(), array2.end()); // 对array2排序int sum1 0, sum2 0;for (int num : array1) sum1 num; // 数组1求和for (int num : array2) sum2 num; // 数组2求和if ((sum1 -sum2) % 2) return {}; // 两个数组的差值必须是偶数int diff (sum1 - sum2) / 2; // 需满足 x - y diffint i 0, j 0, m array1.size(), n array2.size();while (i m j n) { // 双指针寻找满足条件的值if (array1[i] - array2[j] diff) i; else if (array1[i] - array2[j] diff) j;else return {array1[i], array2[j]}; // 找到符合题意得值直接返回两个元素即可}return {}; // 未找到符合题意的两个数}
};
方法三哈希表因为哈希表可以直接查找所以就不需要排序了
class Solution {
public:vectorint findSwapValues(vectorint array1, vectorint array2) {int sum1 0, sum2 0;for (int num : array1) sum1 num;//数组1求和for (int num : array2) sum2 num;//数组2求和if ((sum1 -sum2) % 2) return {}; // 两个数组的差值必须是偶数//将array2的所有元素放入哈希表中unordered_setint arr(array2.begin(), array2.end()); int diff (sum1 - sum2) / 2; //遍历array1for (int x : array1) {//假定当前array1中要交换的是x那么在哈希表中找y如果存在那就可以交换int y x - diff; if (setArr2.count(y)) return {x, y};}return {};}
};
