知名互联网公司校招中常见的算法题（17-18）

旧城等待， 2024-03-22 13:26 13阅读 0赞

##  ##

#### 题目17：寻找两个有序数组的中位数 ####

题目描述：

给定两个大小分别为 m 和 n 的有序数组 nums1 和 nums2，请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

解决思路：

我们可以用二分查找的思想来解决这个问题。首先，我们对两个数组进行切割，将它们分成左右两部分。我们可以将切割线放在 nums1 和 nums2 的中位数上，即将 nums1 切成 nums1\[0:i-1\] 和 nums1\[i:m-1\] 两部分，将 nums2 切成 nums2\[0:j-1\] 和 nums2\[j:n-1\] 两部分。由于两个数组长度之和为偶数，因此左半部分的长度之和应该等于右半部分的长度之和。我们可以保证 nums1\[0:i-1\] 和 nums2\[0:j-1\] 中的所有元素都小于 nums1\[i:m-1\] 和 nums2\[j:n-1\] 中的所有元素。

代码实现：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int m = nums1.length;
      int n = nums2.length;
    if (m > n)
    {
          int[] temp = nums1;
          nums1 = nums2;
          nums2 = temp;
          m = nums1.length;
          n = nums2.length;
      }
      int iMin = 0;
      int iMax = m;
      int halfLen = (m + n + 1) / 2;
      while (iMin <= iMax) {
          int i = (iMin + iMax) / 2;
          int j = halfLen - i;
          if (i < iMax && nums2[j - 1] > nums1[i]) {
              iMin = i + 1;
          } else if (i > iMin && nums1[i - 1] > nums2[j]) {
              iMax = i - 1;
          } else {
              int maxLeft = 0;
              if (i == 0) {
                  maxLeft = nums2[j - 1];
              } else if (j == 0) {
                  maxLeft = nums1[i - 1];
              } else {
                  maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
              }
              if ((m + n) % 2 == 1) {
                  return maxLeft;
              }
              int minRight = 0;
              if (i == m) {
                  minRight = nums2[j];
              } else if (j == n) {
                  minRight = nums1[i];
              } else {
                  minRight = Math.min(nums1[i], nums2[j]);
              }
              return (maxLeft + minRight) / 2.0;
          }
      }
      return 0.0;
    }

题目18：合并两个有序链表

题目描述：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解决思路：

我们可以用迭代的方法来解决这个问题。我们用一个哨兵节点来作为新链表的头节点，用一个指针来遍历两个链表，并将较小的节点加入新链表中。

代码实现：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      ListNode dummy = new ListNode(0);
      ListNode curr = dummy;
      while (l1 != null && l2 != null) {
          if (l1.val < l2.val) {
              curr.next = l1;
              l1 = l1.next;
          } else {
              curr.next = l2;
              l2 = l2.next;
          }
          curr = curr.next;
      }
      if (l1 != null) {
          curr.next = l1;
      }
      if (l2 != null) {
          curr.next = l2;
      }
      return dummy.next;
    }