题目大意:二个数组交换一个元素后,使2个数组的和相等(有多个返回任意一个)

思路分析:

可以把问题分析完,转换成数学问题,列出算式求解

y=(2x-sum1+sum2)/2

int cmp(const void *a, const void *b) {    return *(int *)a - *(int *)b;}int search(int* nums, int numsSize, int target){    int l = 0, r = numsSize - 1;    while(l <= r) {        int mid = (l + r) >> 1;        if(target == nums[mid]) {            return mid;        }else if(target > nums[mid]) {            l = mid + 1;        }else {            r = mid - 1;        }    }    return -1;}int* findSwapValues(int* array1, int array1Size, int* array2, int array2Size, int* returnSize){    int i, x, y, sum1 = 0, sum2 = 0;    int *ret = NULL;    qsort(array1, array1Size, sizeof(int), cmp);       // (1) 数组1递增排序    qsort(array2, array2Size, sizeof(int), cmp);       // (2) 数组2递增排序    for(i = 0; i < array1Size; ++i) {        sum1 += array1[i];                             // (3) 数组1求和    }    for(i = 0; i < array2Size; ++i) {        sum2 += array2[i];                             // (4) 数组2求和    }    for(i = 0; i < array1Size; ++i) {        x = array1[i];        y = 2*x - sum1 + sum2;        if(y & 1) {            continue;                                  // (5) 必须被2整除        }        y >>= 1;                                       // (6) 根据x计算y        if( search(array2, array2Size, y ) != -1) {            ret = (int *)malloc(2 * sizeof(int));      // (7) 返回(x,y);            ret[0] = x;            ret[1] = y;            *returnSize = 2;            return ret;        }    }    *returnSize = 0;    return NULL;}

给定 m × n 矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int x);int binarySearch(int *arr, int arrSize, int x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(int val, int x) {    return val >= x;}int search(int* nums, int n, int target){    int r = binarySearch(nums, n, target);    if(r == n || nums[r] != target)        return -1;    return r;}bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){    int i;    for(i = 0; i < matrixSize; ++i) {        if(-1 != search(matrix[i], matrixColSize, target) ) {            return true;        }    }    return false;}

给你一个严格升序排列的正整数数组arr和一个整数k,找到数组里第K缺失的正整数

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int idx, int x);int binarySearch(int *arr, int arrSize, int x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], mid, x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************//**/int isGreen(int val, int idx, int x) {    return val - (idx+1) >= x;}int findKthPositive(int* arr, int arrSize, int k){    int r = binarySearch(arr, arrSize, k);    return k + r;}

给你四个整数:n. a b c.设计一个算法来找出第n个丑数.抽数是可以被a或b或c整除

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(long long val, int x);int binarySearch(int l, int r, int x) {    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(mid, x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/#define ll long long int A, B, C;int gcd(int a, int b) {    return b == 0 ? a : gcd(b, a % b);     // (1)计算a和b的最大公约数}ll lcm(int a, int b) {    return (ll)a / gcd(a, b) * b;          // (2)计算a和b的最小公倍数}int isGreen(ll val, int x) {               // (3)利用容斥原理判断二分可行性    ll ans = val / A + val / B + val / C - val / lcm(A, B) - val / lcm(B, C) - val / lcm(A, C) + val / lcm(lcm(A, B), C);    return ans >= x;}int nthUglyNumber(int n, int a, int b, int c){    A = a;    B = b;    C = c;    return binarySearch(0, 2000000001, n); // (4)二分枚举找表达式满足的左边界就是答案}

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int num);int binarySearch(int *arr, int arrSize) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], arrSize-mid) )            //  (1) 原本的二分枚举,进行一个修改;            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(int val, int num) {                             return num <= val;                                  // (2)被引用的论文数num小于等于引用次数的val,都是符合条件的}int hIndex(int* citations, int citationsSize){    int ans = binarySearch(citations, citationsSize);   // (3)计算绿色边界    return citationsSize - ans;                         // (4)返回所有绿色元素数目}