【剑指】5.3 时空效率平衡

由于内存成本的下降，现代计算机往往配有充足的内存，所以在处理通常问题时我们更愿意用空间换时间（嵌入式开发和处理海量数据等场景除外）。本节虽然说的时时空平衡，但显然更倾向于优化时间，当然和面试官探讨时空权衡的问题总是好的。

面试题49：丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

如果采用暴力法从1网上搜索每一个整数是否为丑数，直到找出第N个丑数，时间复杂度过大，且搜索了很多不是丑数的数。可以考虑维护一个丑数数组，从小往大，每次把得到的丑数不断乘以2、3、5之后放入他们对应的位置即可。

现在问题的难点就变为了如何将乘出来的丑数放在合适的位置。我们只需要根据当前找到的丑数中的最大值来找下一个数即可，下一个数只可能是由已找到的某数乘2或乘3或乘5得来，这样，我们只要从刚好乘以2、3、5后会大于当前最大丑数的数中比较出乘积最小的那一个放入数组中即可。使用三个指针来分别标记当前乘以2、3、5后会大于数组最大值的数。从三个数乘的结果中选出最小的放入数组并更新对应的指针，那么剩下的指针自然是会大于该数组的最大值。又由于当ugly[i]*2（或3或5）被选为下一个数组的最大值后，下一个乘2（或3或5）大于数组最大值的自然就是ugly[i+1]，更新指针时只需要加一即可。

public int GetUglyNumber_Solution(int index) {
    if (index < 1) return 0;
    int[] ugly = new int[index];
    //初始化第一个丑数
    ugly[0] = 1;
    //指向乘以2、3、5后可能会大于当前最大丑数的位置
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < index; i++) {
        ugly[i] = Math.min(ugly[p2] * 2, Math.min(ugly[p3] * 3, ugly[p5] * 5));
        if (ugly[i] == ugly[p2] * 2) p2++;
        if (ugly[i] == ugly[p3] * 3) p3++;
        if (ugly[i] == ugly[p5] * 5) p5++;
    }
    return ugly[index - 1];
}

面试题50：第一个只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

解题思路

暴力法针对每一个字符都要搜索整个字符串看有没有重复字符，时间复杂度为O(n^2)。我们可以遍历一遍字符串，使用一个哈希表记录某个字符出现的次数，再次遍历就能找到首个只出现一次的字符。由于没有说明是英文字母或ASCII字符，我们只能使用库函数提供的HashMap而不好使用数组。

public int FirstNotRepeatingChar(String str) {
    if(str == null || str.length() == 0) return -1;
    int n = str.length();
    HashMap<Character,Integer> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        char c = str.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    for(int i = 0; i < n; i++){
        if(map.get(str.charAt(i)) == 1) return i;
    }
    return -1;
}

面试题51：数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。

解题思路

如果直接暴力统计，那么时间复杂度为O(n^2)，那么就考虑先比较两个相邻的数字。在归并排序的归并中，比较两个有序子数组的最大值，如果左侧的最大值大于右侧的，则说明左侧最大值和右侧所有的值都构成逆序对，统计该数值并把左侧最大值归并到临时数组中对应位置；否则不统计，只把右侧最大值归并。

一次归并完成后，两个相邻的数组合并成一个有序数组，数组内的数不会再构成逆序对，所有能构成的逆序对已经统计完毕。

class Solution {
    int pairs = 0;
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) return pairs;
        int n = nums.length;
        int[] copy = new int[n];
        mergeSort(nums, copy, 0, n - 1);
        return pairs;
    }

    private void mergeSort(int[] array,int[] copy,int left,int right) {
        if (left >= right) return;
        int mid = left + ((right - left) >> 1);
        mergeSort(array, copy, left, mid);
        mergeSort(array, copy, mid + 1, right);
        merge(array, copy, left, mid, right);
    }

    private void merge(int[] array, int[] copy, int left, int mid, int right) {
        int leftPointer = mid, rightPointer = right, copyIndex = right;
        while (leftPointer >= left && rightPointer >= mid + 1) {
            if (array[leftPointer] > array[rightPointer]) {
                pairs += (rightPointer - mid);
                copy[copyIndex--] = array[leftPointer--];
            } else {
                copy[copyIndex--] = array[rightPointer--];
            }
        }
        while (leftPointer >= left) {
            copy[copyIndex--] = array[leftPointer--];
        }
        while (rightPointer >= mid + 1) {
            copy[copyIndex--] = array[rightPointer--];
        }
        System.arraycopy(copy, left, array, left, right - left + 1);
    }
}

面试题52：两个链表的第一个公共节点

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解题思路

如果采用暴力法比较两个链表中的每一个节点，那么时间复杂度为O(n^2)，比较高。

可以使用两个栈保存两个链表的遍历顺序，最后两个栈的栈顶一定是公共节点，我们同时出栈并比较两个节点，直到首次发现不同的节点，那么上一个节点就是首个公共节点。该方法时间复杂度为O(n)，但是需要O(n)的空间。

还有一种简单的方法是，先遍历一遍得到两个链表的长度与它们的差值X，第二次遍历时使用双指针，更长链表上的指针先走X步，之后两个指针再同步前进，这样首次发现相同的节点就是要找的节点。时间复杂度为O(n)，空间复杂度为O(1)。

上面两种方法都需要注意不存在公共节点和输入节点为空的特殊情况处理。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    int len1 = getLen(pHead1), len2 = getLen(pHead2);
    if (len1 == 0 || len2 == 0) return null;
    int diff = len1 - len2;
    //p1指向长的链表，p2指向短的
    ListNode p1 = diff >= 0 ? pHead1 : pHead2, p2 = diff >= 0 ? pHead2 : pHead1;
    diff = Math.abs(diff);
    while (diff-- > 0) {
        p1 = p1.next;
    }
    while (p1 != null) {
        if (p1.val == p2.val) return p1;
        p1 = p1.next;
        p2 = p2.next;
    }
    return null;
}

private int getLen(ListNode node) {
    int len = 0;
    while (node != null) {
        len++;
        node = node.next;
    }
    return len;
}