头像

蛋蛋の忧伤


访客:739

离线:6个月前



算法1 二分

参考文献

https://www.acwing.com/solution/LeetCode/content/4487/

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       int n = nums1.size(),m = nums2.size();
        if(n > m) {swap(nums1,nums2),swap(n,m);}
        int left = 0,right = n,k = (n + m + 1) >> 1;
        while(left <= right)
        {
            int i = (left + right) >> 1,j = k - i;
            if(i < n && nums1[i] < nums2[j - 1] )
                left = i + 1;
            else if(i > 0 && nums1[i - 1] > nums2[j])
                right = i - 1;
            else
            {
                int max_left,min_right;
                if(i == 0) max_left = nums2[k - 1];
                else if(j == 0) max_left = nums1[k - 1];
                else max_left = max(nums1[i - 1],nums2[j - 1]);
                if((n + m) % 2 == 1) return max_left;

                if(i == n) min_right = nums2[j];
                else if(j == m) min_right = nums1[i];
                else min_right = min(nums1[i],nums2[j]);
                return (max_left + min_right)/2.0;
            }
        }
        return 0.0;
    }
};

算法1延伸

参考文献

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(),m = nums2.size();
        if(n > m) {swap(nums1,nums2),swap(n,m);}

        int left = 0,right = n * 2;
        int leftMax1, leftMax2, rightMin1, rightMin2;
        int i, j;

        while (left <= right) {
            i = (left + right) >> 1;
            j = m + n -i;

            leftMax1 = (i == 0) ? INT_MIN :nums1[(i - 1) /2];
            rightMin1 = (i == n * 2) ? INT_MAX : nums1[i /2];
            leftMax2 = (j == 0) ? INT_MIN : nums2[(j - 1) / 2];
            rightMin2 = (j == m * 2) ? INT_MAX :nums2[ j / 2];

            if (leftMax2 > rightMin1)
                left = i + 1;
            else if (leftMax1 > rightMin2)
                right = i - 1;
            else 
                break;            
        }
        return (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2.0;
    }
};

算法2 分治法

参考文献

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size(), len = len1 + len2;
        if (len % 2 == 0) {
            int left = getKthSmallest(nums1, 0, nums2, 0, len / 2);
            int right = getKthSmallest(nums1, 0, nums2, 0, len / 2 + 1);
            return (left + right) / 2.0;
        }
        else
            return getKthSmallest(nums1, 0, nums2, 0, len / 2 + 1);
    }    

    int getKthSmallest(vector<int> &nums1, int start1, vector<int> &nums2, int start2, int k) {
        if (nums1.size() - start1 > nums2.size() - start2)
            return getKthSmallest(nums2, start2, nums1, start1, k);
        if (start1 == nums1.size()) 
            return nums2[start2 + k -1];
        if (k == 1)
            return min(nums1[start1], nums2[start2]);

        //缩小范围
        int s1 = start1 + min(k / 2, int(nums1.size() - start1));
        int s2 = start2 + min(k / 2, int(nums2.size() - start2));
        if (nums1[s1 - 1] > nums2[s2 - 1])
            return getKthSmallest(nums1, start1, nums2, s2, k - (s2 - start2));
        else
            return getKthSmallest(nums1, s1, nums2, start2, k - (s1 - start1));
    }
};

算法2 分治法延伸

参考文献

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size(), len = len1 + len2;
        int left = (len + 1) / 2;
        int right = (len + 2) /2;  
        return (getKthSmallest(nums1, 0, nums2, 0, left) + getKthSmallest(nums1, 0, nums2, 0, right)) / 2.0;         
    }    

    int getKthSmallest(vector<int> &nums1, int start1, vector<int> &nums2, int start2, int k) {
        if (nums1.size() - start1 > nums2.size() - start2)
            return getKthSmallest(nums2, start2, nums1, start1, k);
        if (start1 == nums1.size()) 
            return nums2[start2 + k -1];
        if (k == 1)
            return min(nums1[start1], nums2[start2]);

        //缩小范围
        int s1 = start1 + min(k / 2, int(nums1.size() - start1));
        int s2 = start2 + min(k / 2, int(nums2.size() - start2));
        if (nums1[s1 - 1] > nums2[s2 - 1])
            return getKthSmallest(nums1, start1, nums2, s2, k - (s2 - start2));
        else
            return getKthSmallest(nums1, s1, nums2, start2, k - (s1 - start1));
    }
};



C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //增加一个头结点指针
        ListNode* headPtr = new ListNode(0);
        headPtr->next = head;
        // 增加一个游标
        ListNode* cur = headPtr;

        //标记前后两个要交换的节点
        ListNode* first = NULL;
        ListNode* second = NULL;

        //遍历所有节点
        while (cur->next != NULL) {
            first = cur->next;
            if (first == NULL)
                break;
            second = first->next;
            if (second == NULL)
                break;
            //交换节点
            cur->next = second;
            first->next = second->next;
            second->next = first;
            cur = first;
        }

        return headPtr->next;
    }
};