423.LeetCode

两数之和

方法一：暴力枚举

时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

空间复杂度：O(1)。

var Solution = function(nums,target){
	const sorted = new Array(2).fill(0);
	for(let i = 0;i<nums.length;++i){
		for(let j = i+1;j<nums.length;++j){
			if(nums[j]+nums[i]==target){
				sorted[0] = i;
				sorted[1] = j;
				return sorted;
			}
		}
	}
	return sorted;
};
复制代码

方法二：哈希表

时间复杂度：O(N)，其中 NN 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target – x。

空间复杂度：O(N)，其中 NN 是数组中的元素数量。主要为哈希表的开销。

class Solution{
	public int[] twoSum(int[] nums, int target){
		Map<Interger,Interger>hashtable = new HashMap<Interger,Interger>();
		for(int i = 0;i < nums.length; ++i){
			if(hashtable.containsKey(target - numms[i])){
				return new int[]{hashtable.get(target - nums[i]),i};
			}
			hashtable.put(nums[i],i);
		}
		return new int[0];
	}
}
复制代码

数组中的第K个最大元素

方法一：基于快速排序的选择方法

我们可以用快速排序来解决这个问题，先对原数组排序，再返回倒数第 k 个位置，这样平均时间复杂度是$O(n \log n)$，但其实我们可以做的更快。

首先我们来回顾一下快速排序，：从子数组 $a[l \cdots r]$中选择任意一个元素 x 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， x的最终位置就是 q。

由此可以发现每次经过「划分」操作后，我们一定可以确定一个元素的最终位置，即 x 的最终位置为 q，并且保证$a[l \cdots q – 1]$ 中的每个元素小于等于 a[q]，且 a[q] 小于等于$a[q + 1 \cdots r]$ 中的每个元素。所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案。 我们只关心这一点，至于 $a[l \cdots q – 1]$和 $a[q+1 \cdots r]$是否是有序的，我们不关心。

class Solution{
	Random random = new Random();
	public int findKthLargest(int[] nums, int k){
		return quickSelect(nums,0,nums.length-1,nums.length-k);
	}
	public int quickSelect(int[] a,int l,int r,int index){
		int q = randomPartition(a,l,r);
		if(q == index){
			return a[q];
		}else{
			return q< index?quickSelect(a,q+1,r,index):quickSelect(a,l,q-1,index);
		}
	}
	public int randomPartition(int[] a,int l,int r){
		int i = random.nextInt(r-l+1)+1;
		swap(a,i,r);
		return Partition(a,l,r);
	}
	public int Partition(int[]a,int l,int r){
		int x = a[r],i = l-1;
		for(int j = 1;j<r;++j){
			if(a[j]<=x){
				swap(a,++i,j);
			}
		}
		swap(a,i+1,r);
		return i+1;
	}
	public void swap(int[]a,int i,int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}
复制代码

时间复杂度：$O(n)$

空间复杂度：$O(\log n)$，递归使用栈空间的空间代价的期望为 $O(\log n)$。

方法二：基于堆排序的选择方法

建立一个大根堆，做$k – 1$ 次删除操作后堆顶元素就是我们要找的答案。

class Solution{
	public int findKthLargest(int[] nums, int k){
		int heapSize = nums.length;
		buildMaxHeap(nums,heapSize);
		for(int i = nums.length - 1;i>=nums.length-k+1;--i){
			swap(nums,0,i);
			--heapSize;
			maxHeapify(nums,0,heapSize);
		}
		return nums[0];
	}
	public void buildMaxHeap(int[] a,int heapSize){
		for(int i = heapSize/2;i>=0;--i){
			maxHeapify(a,i,heapSize);
		}
	}
	public void maxHeapify(int[] a;int i;int heapSize){
		int l = i*2+1,r = i*2+2,largest = i;
		if(l<heapSize&&a[l]>a[largest]){
			largest = l;
		}
		if(r<heapSize&&a[r]>a[largest]){
			largest = r;
		}
		if(larget != i){
			swap(a,i,largest);
			maxHeapify(a,largest,heapSize);
		}
	}
	public void swap(int[] a,int i,int j){
		int temp = a[i];
		a[i]=a[j];
		a[j]=temp;
	}
}
复制代码

时间复杂度：$O(n \log n)$，建堆的时间代价是 $O(n)$，删除的总代价是 $O(k \log n)$，因为 $k < n$，故渐进时间复杂为$O(n + k \log n) = O(n \log n)$。

空间复杂度：$O(\log n)$，即递归使用栈空间的空间代价。

相交链表

方法一: 暴力法

对链表A中的每一个结点 $a_i$，遍历整个链表B并检查链表B中是否存在结点和$a_i$相同。

复制代码

时间复杂度 : $(mn)$。
空间复杂度 :$O(1)$。

方法二: 哈希表法

遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点$b_i$是否在哈希表中。若在，则$b_i$为相交结点。

import java.util.HashSet;
import java.util.Set;

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> hashSet = new HashSet<>();

        ListNode curNode = headA;
        while (curNode != null) {
            hashSet.add(curNode);
            curNode = curNode.next;
        }

        curNode = headB;
        while (curNode != null) {
            if(hashSet.contains(curNode)){
                return curNode;
            }
            curNode = curNode.next;
        }
        return null;
    }
}

复制代码

时间复杂度 : $O(m+n)$。
空间复杂度 : $O(m)$ 或 $O(n)$。

方法三：双指针法

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 特判
        if (headA == null || headB == null) {
            return null;
        }

        ListNode head1 = headA;
        ListNode head2 = headB;

        while (head1 != head2) {
            if (head1 != null) {
                head1 = head1.next;
            } else {
                head1 = headB;
            }

            if (head2 != null) {
                head2 = head2.next;
            } else {
                head2 = headA;
            }
        }
        return head1;
    }
}
复制代码

时间复杂度 : O(m+n)。
空间复杂度 : O(1)。