admin 发布的文章

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

解法

1、查找第k小的数
对于数组A，前p个元素A[0]、A[1]、...、A[p-1]，有p-1个元素不大于A[p-1]，同样，对于数组B，前k-p个元素B[0]、B[1]、...、B[k-p-1]，有k-p-1个元素不大于B[k-p-1]。比较A[p-1]和B[k-p-1]存在三种情况：
1) 若A[p-1] = B[k-p-1]，那么共有(p-1)+(k-p-1)+1=k-1个元素不大于A[p-1]，即A[p-1]是第k小的数；
2) 若A[p-1] < B[k-p-1]，那么第k小的数不可能在区间A[0,p-1]之内。反证法证明：不妨设A[p-1]是第k小的数，也就是说最多只有p-1个数不比它大，而B[k-p-1]大于A[p-1]，所以B[k-p-1]之后的所有数都大于A[p-1]，这样即使B[k-p-1]之前的所有数都不比A[p-1]大，B中也只能找到k-p-1个数不比A[p-1]大，那么A和B中最多只有(p-1)+(k-p-1)=k-2个数不大于A[p-1]，因此A[p-1]不可能是第k小的数；同样的，B[k-p-1]之后的数也不可能是第k小的数，因为它至少是B[k-p]，前面有k-p个数不比B[k-p]大，再加上A[0,p-1]有p个数不比B[k-p]大，因此至少有k-p+p=k个数不比B[k-p]大，也就是说B[k-p]至少是第k+1小的数。舍弃区间之后，问题就变成寻找第k-p小的数。
3) 若A[p-1] > B[k-p-1]，同理可舍去B[0,k-p-1]区间和A[p-1]之后的区间。

2、查找中位数
如果合并后的总元素个数为奇数，则中位数的下标是n/2+1，如果为偶数，则中位数是下标n/2和下标n/2+1两个元素的平均值。

参考资料

https://blog.csdn.net/lxhpkm01/article/details/53823595
https://www.cnblogs.com/davidluo/articles/k-smallest-element-of-two-sorted-array.html
#include <stdio.h>

int findMedian(int *a, int m, int *b, int n);
int findk(int *a, int m, int *b, int n, int k);

int main()
{
    int a[] = {1,3,5,7,9};
    int b[] = {2,4,6,8};
    int m = sizeof(a)/sizeof(int);
    int n = sizeof(b)/sizeof(int);
    int median;

    median = findMedian(a,m,b,n);
    printf("the median is: %d\n",median);

    return 0;
}

/**
 * 查找中位数
 */
int findMedian(int *a, int m, int *b, int n)
{
    int len = m + n;

    if ((len&1) == 0) { // len 为偶数
        return (findk(a,m,b,n,len/2) + findk(a,m,b,n,len/2+1))/2;
    } else { // len 为奇数
        return findk(a,m,b,n,len/2+1);
    }
}

/**
 * 查找第k小的数
 */
int findk(int *a, int m, int *b, int n, int k)
{
    if (m == 0) {
        return b[k-1];
    }
    if (n == 0) {
        return a[k-1];
    }
    if (k == 1) {
        return a[0] < b[0] ? a[0] : b[0];
    }

    if (m > n) {
        return findk(b,n,a,m,k);
    }

    int i = m < k/2 ? m : k/2;
    int j = k - i;

    if (a[i-1] == b[j-1]) {
        return a[i-1];
    } else if (a[i-1] < b[j-1]) {
        return findk(a+i,m-i,b,j,k-i);
    } else {
        return findk(a,i,b+j,n-j,k-j);
    }
}

Given a string, find the length of the longest substring without repeating characters.

解法

滑动窗口
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int longestSubstring(char *s);
int max(int a, int b);

int main()
{
    char *s = "abcabcbb";
    int length;

    length = longestSubstring(s);
    printf("The length of longest substring is: %d\n", length);

    return 0;
}

int longestSubstring(char *s)
{
    int start,end;
    int len = strlen(s); // 字符串长度
    int lenW; // 滑动窗口长度
    char window[128]; // 滑动窗口内的字符
    int pos[128]; // 滑动窗口内的字符在原字符串的位置
    int p,i,flag;
    int length = 0;

    memset(window,0,128*sizeof(char));
    memset(pos,0,128*sizeof(int));
    
    for (start = 0, end = 0; end < len; end++)
    {
        flag = 0;
        p = 0;
        lenW = strlen(window);
        for (i = 0; i < lenW; i++)
        {
            if (window[i] == s[end])
            {
                flag = 1;
                p = pos[i];
                break;
            }
        }
        if (flag)
        {
            start = p + 1;
        }

        length = max(length, end-start+1);
        
        memset(window,0,128*sizeof(char));
        memset(pos,0,128*sizeof(int));
        for (i = 0, p = start; p <= end; p++)
        {
            window[i] = s[p];
            pos[i] = p;
            i++;
        }
    }
    
    return length;
}

int max(int a, int b)
{
    return a > b ? a : b;
}
  1. 1
  2. 2