ARTS 打卡 第 2 周

用户头像
引花眠
关注
发布于: 2020 年 06 月 01 日

ARTS简介

Algorithm 是一道算法题,Review 是读一篇英文文章,Technique/Tips 是分享一个小技术,Share 是分享一个观点。

Algorithm

Lecode-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),每个服务都有自己的数据库,每个服务都是由一组相关的组件构成。

其好处是:

  1. 很容易持续发布 每个服务测试简单;每个服务能被单独发布;每个服务由单独的团队负责; 每个服务单独演化

  2. 每个服务相对较小 很容易理解;快速的启动时间;IDE操作容易

  3. 问题隔离 单独的服务故障,不会导致整个应用故障

  4. 方便使用新技术 用新技术重写服务相对容易;新增的服务很容易使用新技术。

微服务也有很多需要解决的难点:

  1. 如何构建日益复杂的分布式系统 IDE对分布式不提供支持;很难测试整个应用; 必须实现跨服务通讯机制;必须实现分布式事物;跨服务用例必须在多个团队之间协调;

  2. 如何发布 复杂的发布过程;协调多个微服务发布。

  3. 增长的内存消耗 单个微服务比整个单体应用内存消耗小,但是所有微服加起来消耗会增大。

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 日 阅读数: 34
用户头像

引花眠

关注

还未添加个人签名 2018.06.11 加入

还未添加个人简介

评论

发布
暂无评论
ARTS打卡 第2周