ARTS 打卡第 2 周

关注
发布于: 2020 年 06 月 01 日
ARTS简介Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
AlgorithmLecode-4 寻找两个正序数组的中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
力扣（LeetCode）4.寻找两个正序数组的中位数
解题思路：
我们假设这两个数组分别是a[m]和b[n]，那么这两个数组的总长度为n+m
当n+m为偶数时，我们要找的中位数是第(n+m+1)/2与(n+m+1)/2+1个元素的平均数
当n+m为奇数时，我们要找的中位数是第(n+m+1)/2个元素。
看到要求算法的时间复杂度为 O(log(m + n))，第一反应是二分查找，那么如何查找呢？
数组元素为：a[1],a[2],a[3],…,a[m]，b[1],b[2],b[3],…,b[n]，以下m、n分别表示数组a、b的长度。
假设m<n，令k = (m+n+1)/2，则在a和b中查找第k/2个元素
a[1],a[2],a[3],…,a[k/2],…a[m]
b[1],b[2],b[3],…,b[k/2],…b[n]
第一种情况：如果a[k/2]<b[k/2]，在a数组中有(k/2)-1个数比a[k/2]小，b数组中也有(k/2)个数比a[k/2]小（包括b[k/2]），所以有(k/2)-1+(k/2)=k-1个数比b[k/2]小，而在b数组中比a[k/2]小的个数至多有(k/2)-1个，a数组中有(k/2)-1个数比a[k/2]小，所以至多有(k/2)-1+(k/2)-1=k-2个数比a[k/2]小，在此种情况下a[1],a[2],a[3],...,a[k/2]这些元素都不可能是第k个元素，可以排除，然后在a[k/2+1],...a[m]与b[1],...b[n]中寻找第(m+n+1)/2-k/2个元素（已经排除k/2个元素了），此时令a=a[k/2+1],...a[m]，b=b[1],...b[n]，k=(m+n+1)/2-k/2；如果m<k/2，则能排除的元素只m个元素。
第二种情况：如果a[k/2]==b[k/2]，可以当成第一种情况
第三种情况：如果a[k/2]>b[k/2]，可以排除b[1],b[2],b[3],...,b[k/2]
特殊情况：
若m==0，则返回b[k]；
若k==1，则返回a[0]与b[0]中的最小值
第一版代码，时间O(log(m+n))，但是每次递归都会生成额外的数组。
public class MedianNumber {
/**
     * O(log(m+n))
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianInSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        double median;
        if ((m + n) % 2 == 0) {
            median = (getKth(nums1, nums2, (m + n + 1) / 2) + getKth(nums1, nums2, (m + n + 1) / 2 + 1)) / 2.0;
        } else {
            median = (getKth(nums1, nums2, (m + n + 1) / 2));
        }
        return median;
    }
    private static int getKth(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if (len1 > len2) {
            // 保证 m<n nums1.length < nums2.length
            return getKth(nums2, nums1, k);
        }
        // 若m==0，则中位数就是b[k]，终止；
        if (len1 == 0) {
            return nums2[k - 1];
        }
        // 若k==1，则返回a[0]与b[0]中的最小值
        if (k == 1) {
            return Math.min(nums1[0], nums2[0]);
        }
        int i = Math.min(len1, k / 2) - 1;
        int j = Math.min(len2, k / 2) - 1;
        if (nums1[i] <= nums2[j]) {
            return getKth(Arrays.copyOfRange(nums1, i + 1, nums1.length), nums2, k - (i + 1));
        } else {
            return getKth(nums1, Arrays.copyOfRange(nums2, j + 1, nums2.length), k - (j + 1));
        }
    }
}
第二版，不是每次都复制数组，而是移动指针
public class MedianNumber {
/**
     * O(log(m+n))
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianInSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        double median = 0.0;
        if ((m + n) % 2 == 0) {
            median = (getKthElement(nums1, 0, nums2, 0, (m + n + 1) / 2)
                    + getKthElement(nums1, 0, nums2, 0, (m + n + 1) / 2 + 1)) / 2.0;
        } else {
            median = (getKthElement(nums1, 0, nums2, 0, (m + n + 1) / 2));
        }
        return median;
    }
    private static int getKthElement(int[] nums1, int start1, int[] nums2, int start2, int k) {
        int len1 = nums1.length - start1;
        int len2 = nums2.length - start2;
        if (len1 > len2) {
            // 保证 m<n nums1.length < nums2.length
            return getKthElement(nums2, start2, nums1, start1, k);
        }
        // 若m==0，则中位数就是b[k]，终止；
        if (len1 == 0) {
            return nums2[start2 + k - 1];
        }
        // 若k==1，则返回a[0]与b[0]中的最小值
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;
        // 在实际中不需要复制数组，移动指针就行
        if (nums1[i] <= nums2[j]) {
            return getKthElement(nums1, i + 1, nums2, start2, k - (i - start1 + 1));
        } else {
            return getKthElement(nums1, start1, nums2, j + 1, k - (j - start2 + 1));
        }
    }
}
Review学习-微服务架构模式系列，网站地址是：https://microservices.io
微服务架构-Pattern: Microservice Architecture
这篇文章的主要介绍了微服务架构模式：
微服务模式是实现应用的一种模式，他将应用分解为一组松耦合，相互协调调用的服务，服务之间可以使用不同的协议调用（HTTP/REST、AMQP），每个服务都有自己的数据库，每个服务都是由一组相关的组件构成。
其好处是：
很容易持续发布 每个服务测试简单；每个服务能被单独发布；每个服务由单独的团队负责； 每个服务单独演化
每个服务相对较小 很容易理解；快速的启动时间；IDE操作容易
问题隔离 单独的服务故障，不会导致整个应用故障
方便使用新技术 用新技术重写服务相对容易；新增的服务很容易使用新技术。
微服务也有很多需要解决的难点：
如何构建日益复杂的分布式系统 IDE对分布式不提供支持；很难测试整个应用； 必须实现跨服务通讯机制；必须实现分布式事物；跨服务用例必须在多个团队之间协调；
如何发布 复杂的发布过程；协调多个微服务发布。
增长的内存消耗 单个微服务比整个单体应用内存消耗小，但是所有微服加起来消耗会增大。
Tips记录我对于Linux的学习，从磁盘相关的命令开始：
ps:”~” 表示为 home 目录，”.” 则是表示目前所在的目录，”..” 则表示当前目录的上一层目录
df 命令，用于显示目前在Linux系统上的文件系统的磁盘使用情况统计
df
文件系统                         1K-块      已用      可用      已用% 挂载点
udev                           8111132         0   8111132    0% /dev
tmpfs                          1632932      2264   1630668    1% /run
/dev/mapper/root_swap-lvroot  80589296    114424  76338120    1% /
#第一列指定文件系统的名称，第二列指定一个特定的文件系统1K-块1K是1024字节为单位的总内存。已用、可用、挂载点顾名思义。
df -h
文件系统                        容量   已用  可用    已用% 挂载点
udev                          7.8G     0  7.8G    0% /dev
tmpfs                         1.6G  2.3M  1.6G    1% /run
/dev/mapper/root_swap-lvroot   77G  112M   73G    1% /
# -h 用人类可读的格式展示(G（千兆字节），M（兆字节）,K（千字节）)，大部分命令有这个参数
Share分享最近对计算机基础的复习，这次分享的是信息的表示与存储-整数的表示，可能会有不足之处，之后会根据理解继续修改。
﻿
发布于: 2020 年 06 月 01 日阅读数: 53
原文链接:【http://xie.infoq.cn/article/6aea8cd6918a01cd768e406f9】。
引花眠

关注
还未添加个人签名 2018.06.11 加入
还未添加个人简介
发布
暂无评论
创作场景

ARTS 打卡 第 2 周

ARTS简介

Algorithm

Review

Tips

Share

引花眠

评论

ARTS 打卡第 2 周
