Kotlin实现LeetCode算法题之Median of Two Sorted Arrays

 

题目Median of Two Sorted Arrays（难度Hard）

 

 

方案1，数组合并&排序调用Java方法

1 import java.util.* 2 3 class Solution { 4 fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double { 5 val lenNums1 = nums1.size 6 val lenNums2 = nums2.size 7 8 val array = Arrays.copyOf(nums1, lenNums1 + lenNums2) 9 System.arraycopy(nums2, 0, array, lenNums1, lenNums2) 10 11 Arrays.sort(array) 12 13 var median: Double 14 val lenArray = array.size 15 if (lenArray % 2 == 1) { 16 median = array[(lenArray - 1) / 2].toDouble() 17 } else { 18 median = (array[(lenArray - 1) / 2] + array[lenArray / 2]).toDouble() / 2 19 } 20 21 return median 22 } 23 }

 

提交详情1

 

平均耗时0.25ms。

 

方案2，数组合并&排序调用Kotlin方法

1 class Solution { 2 fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double { 3 val lenNums1 = nums1.size 4 val lenNums2 = nums2.size 5 6 val array = IntArray(lenNums1 + lenNums2) 7 System.arraycopy(nums1, 0, array, 0, lenNums1) 8 System.arraycopy(nums2, 0, array, lenNums1, lenNums2) 9 10 array.sort() 11 12 var median: Double 13 val lenArray = array.size 14 if (lenArray % 2 == 1) { 15 median = array[(lenArray - 1) / 2].toDouble() 16 } else { 17 median = (array[(lenArray - 1) / 2] + array[lenArray / 2]).toDouble() / 2 18 } 19 20 return median 21 } 22 }

 

提交详情2

平均耗时0.27ms。

 

Java & Kotlin代码对比

其实，通过源码可以发现，方案1和2在对数组进行合并与排序时调用的方法是一样的。

Arrays.java

1 public static int[] copyOf(int[] original, int newLength) { 2 int[] copy = new int[newLength]; 3 System.arraycopy(original, 0, copy, 0, 4 Math.min(original.length, newLength)); 5 return copy; 6 }

 copyOf方法内部调用的还是System的静态方法arraycopy（native就不往下追了）。

 

System.java

1 public static native void arraycopy(Object src, int srcPos, 2 Object dest, int destPos, 3 int length);

 

Arrays.kt

1 /** 2 * Creates a new array of the specified [size], where each element is calculated by calling the specified 3 * [init] function. The [init] function returns an array element given its index. 4 */ 5 public inline constructor(size: Int, init: (Int) -> Int)

IntArray(size: Int)会生成一个大小为size，元素值由init方法利用下标值计算而来，如果init不传入，那么默认均为0。

 

Arrays.kt

1 public fun IntArray.sort(): Unit { 2 if (size > 1) java.util.Arrays.sort(this) 3 }

Kotlin中IntArray的扩展方法sort，内部调用的是Java中Arrays的sort方法。

 

Arrays.java

1 public static void sort(int[] a) { 2 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 3 }

Arrays的sort方法最终是通过快排来实现的。而快速排序的时间复杂度为O(nlog(n))，但是题目要求量级为O(log(m+n))。

 

方案3，分治法求中位数

1 class Solution { 2 fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double { 3 var media1: Int 4 var media2 = 0 5 val len1 = nums1.size 6 val len2 = nums2.size 7 8 if ((len1 + len2) % 2 == 1) { 9 media1 = getMedian(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) / 2 + 1) 10 return media1 / 1.0 11 } else { 12 media1 = getMedian(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) / 2) 13 media2 = getMedian(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) / 2 + 1) 14 return (media1 + media2) / 2.0 15 } 16 } 17 18 fun getMedian(nums1: IntArray, nums2: IntArray, s1: Int, n1: Int, s2: Int, n2: Int, k: Int): Int { 19 val x = (s1 + n1) / 2 20 val y = (s2 + n2) / 2 21 22 23 if (s1 > n1) 24 return nums2[s2 + k - 1] 25 26 if (s2 > n2) 27 return nums1[s1 + k - 1] 28 29 return if (nums1[x] <= nums2[y]) { 30 if (k <= x - s1 + (y - s2) + 1) { 31 getMedian(nums1, nums2, s1, n1, s2, y - 1, k) 32 } else { 33 getMedian(nums1, nums2, x + 1, n1, s2, n2, k - (x - s1) - 1) 34 } 35 } else { 36 if (k <= x - s1 + (y - s2) + 1) { 37 getMedian(nums1, nums2, s1, x - 1, s2, n2, k) 38 } else { 39 getMedian(nums1, nums2, s1, n1, y + 1, n2, k - (y - s2) - 1) 40 } 41 } 42 } 43 }

 

提交详情3

平均耗时0.32ms。

 

结果分析

但从LeetCode的测试用例所消耗的时间来看，上述三种方案没有明显的区别，理论上分治法的时间复杂度为O(log(n))。

转载于:https://www.cnblogs.com/tgyf/p/7810376.html

总结

以上是生活随笔为你收集整理的Kotlin实现LeetCode算法题之Median of Two Sorted Arrays的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。