Sort 合集

发表于

Intersection of Two Arrays

Question

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Analysis

两个HashSet分别用于找Intersection和存储不重复结果

时间复杂度 ：O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> res=new HashSet<Integer>();
        Set<Integer> set=new HashSet<Integer>();
        for(int i:nums1){
            set.add(i);
        }
        for(int j:nums2){
            if(set.contains(j))
                res.add(j);
        }
        int[] result=new int[res.size()];
        int m=0;
        for(int tmp:res){
            result[m++]=tmp;
        }
        return result;
    }
}

Intersection of Two Arrays II

Question

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Analysis

  • 将两个数组排序之后利用两个指针跟踪两个数组的元素进行比较，相等时加入结果，否则较小的数字方的指针向下移动。
  • 或者不排序，利用HashMap来记录每个元素的出现次数，每遇到重复便将次数-1

Answer To Third Follow Up Question

  1. 假如只有nums2不能放入内存中，则将nums1放入HashMap中，每次从disk中读取恰巧可以放入内存中大小的数据，记录intersection
  2. 假如nums1 与 nums2 均不能放入内存中，则对其分别利用外排(external sort)进行排序,则每次读取比如2G的数据（内存中可以放的下的大小），利用Two Pointers找到intersection，循环执行这个步骤直至没有数据可比较。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> res=new ArrayList<Integer>();
        int i=0,j=0;
        while(i<nums1.length&&j<nums2.length){
            if(nums1[i]==nums2[j]){
                res.add(nums1[i]);
                i++;
                j++;
            }else if(nums1[i]<nums2[j]){
                i++;
            }else{
                j++;
            }
        }
        
        int m=0;
        int[] result=new int[res.size()];
        for(int tmp:res){
            result[m++]=tmp;
        }
        return result;
    }
}

Shorter Version

1
2
3
4
5
6
7
8
9
10
public int[] intersection(int[] nums1, int[] nums2) {
    int k = 0, l1 = nums1.length, l2 = nums2.length;
    int[] result = new int[l1];
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    for (int i = 0, j = 0; i < l1 && j < l2;)
        if (nums1[i] < nums2[j]) i++;
        else if (nums1[i] == nums2[j++]) result[k++] = nums1[i++];
    return Arrays.copyOf(result, k);
}

H-Index

H Index I/ II

桶排序思想

Valid Anagram

Question

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Analysis

利用int数组记录每个字母出现的次数，第一个串遍历的过程中++，第二个串遍历的过程中- - ，最后判断是否数组中所有的元素均为0.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] letter=new int['z'+1];
        for(int i=0;i<s.length();i++)
            letter[s.charAt(i)]++;
        for(int j=0;j<t.length();j++)
            letter[t.charAt(j)]--;
        for(int k='a';k<='z';k++){
            if(letter[k]!=0)
                return false;
        }
        return true;
    }
}

Largest Number

Largest Number

Sort List

Question

Sort a linked list in O(n log n) time using constant space complexity.

Analysis

时间复杂度 O(n) 空间复杂度 O(logn)

调用了log(length)次Merge

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
  
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    // step 1. cut the list to two halves
    ListNode prev = null, slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
      prev = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    
    prev.next = null;
    
    // step 2. sort each half
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    // step 3. merge l1 and l2
    return merge(l1, l2);
  }
  
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode l = new ListNode(0), p = l;
    
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }
    
    if (l1 != null)
      p.next = l1;
    
    if (l2 != null)
      p.next = l2;
    
    return l.next;
  }
}

Insertion Sort List || Sort List

List Sort Series

Sort Colors

Question

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Analysis

在五个月内做了三遍的题还是一直在错，基本思想是red，blue两个指针，将元素0，2分别交换到数组首和末尾。

  • 交换的循环条件是i小于等于blue的指针
  • 由于停止的条件是i<=blue，所以应该先交换blue，后交换red

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public void sortColors(int[] nums) {
        int zero=0,two=nums.length-1;
        for(int i=0;i<=two;i++){
            while(nums[i]==2&&i<two)  swap(nums,i,two--);
            while(nums[i]==0&&i>zero)  swap(nums,i,zero++);
        }
    }
    
    private void swap(int[] nums, int a, int b){
        int tmp=nums[a];
        nums[a]=nums[b];
        nums[b]=tmp;
    }
}

Insert Interval||Merge Intervals

Answer

注意所给区间均为闭区间，所以在控制边界调节时（合并等）在等号成立的时候也需要执行。