2019-10-11 刷题总结 -- sort
2019-10-11 本文已影响0人
Leahlijuan
- sort list
这道题实在是有点繁琐，要求sort一个LinkedList，并且runtime是O(n lg n），space complexity必须是constant。从runtime来筛选的话，可以用merge sort和heap sort，但是heap sort必须是有index的情况才可以使用，因为heap sort必须通过index得到left right。因此，这里只能用mergesort。但是考虑到space complexity的要求，无法使用一般的recursion形式的mergesort，必须是in place。
看了discussion的答案好久才想明白。
还是用比较经典的merge sort思路，只不过split这一步，是根据长度截取两段left和right，与此同时要记下下一次要开始截取的点。截取了left right之后将这两段merge。这里的变化因素就是截取的长度，长度每次翻倍，1，2，4，。。。
每次长度变化都从头开始，重复一边split和merge的过程。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
// cannot use heapsort because we cannot get the left and right by index
// so consider about inplace mergesort
// mergesort
if (head == null || head.next == null) {
return head;
}
// get the length of the linked list
int len = 0;
ListNode dummy = new ListNode(0);
dummy.next = head;
while (head != null) {
head = head.next;
len++;
}
// split and merge here
for (int i = 1; i < len; i <<= 1) {
ListNode tail = dummy;
ListNode cur = dummy.next;
while (cur != null) {
ListNode left = cur;
ListNode right = split(left, i);
cur = split(right, i);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
// cut length of step of the LinkedList for head;
// return the begining of this part, set the end of length n linkedlist null
public ListNode split(ListNode head, int step) {
if (head == null) {
return null;
}
while (step > 1 && head.next != null) {
head = head.next;
step--;
}
ListNode res = head.next;
head.next = null;
return res;
}
// merge two split part, and then append to the tail
// return the tail of merged linkedlist
public ListNode merge(ListNode left, ListNode right, ListNode end) {
ListNode tail = end;
while (left != null && right != null) {
if (left.val < right.val) {
tail.next = left;
left = left.next;
} else {
tail.next = right;
right = right.next;
}
tail = tail.next;
}
if (left != null) {
tail.next = left;
}
if (right != null) {
tail.next = right;
}
while (tail.next != null) {
tail = tail.next;
}
return tail;
}
}
-
Merge Two Sorted Lists
这题太简单。。。必须一遍过 -
Merge Intervals
也不难。我写了两种解法，一种解法需要一个list作为过渡，另一种不需要。
// need another list
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <2) {
return intervals;
}
Arrays.sort(intervals, (a,b)->(a[0]-b[0]));
List<int[]> res = new ArrayList<>();
int[] prev = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] > prev[1]) {
res.add(prev);
prev = intervals[i];
} else {
prev[1] = Math.max(prev[1], intervals[i][1]);
}
}
res.add(prev);
int[][] arr = new int[res.size()][2];
arr = res.toArray(arr);
return arr;
}
}
// do not need another list
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) {
return intervals;
}
Arrays.sort(intervals, (a,b)->(a[0]-b[0]));
// two pointers, first point to the arranged
int i = 0;
for (int j = 1; j < intervals.length; j++) {
if (intervals[i][1] < intervals[j][0]) {
i++;
intervals[i] = intervals[j];
} else {
intervals[i][1] = Math.max(intervals[i][1],intervals[j][1]);
}
}
int[][] res = Arrays.copyOfRange(intervals, 0, i + 1);
return res;
}
}
- Insertion Sort List
用insertion sort的方法sort一个linkedlist。因为linkedlist没法往前，所以从最后开始sort。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
int len = 0;
while (head != null) {
head = head.next;
len++;
}
for (int i = len-1; i > 0; i--) {
ListNode cur = forward(dummy, i);
sort(cur);
}
return dummy.next;
}
public ListNode forward(ListNode head, int i) {
while(i > 0) {
head = head.next;
i--;
}
return head;
}
public void sort(ListNode cur) {
int val = cur.val;
while (cur.next != null) {
if (val > cur.next.val) {
cur.val = cur.next.val;
cur = cur.next;
} else {
break;
}
}
cur.val = val;
}
}
另一种方法就是还是按照原本的insertion sort的方法，只不过每次不是往前对比，而是从头开始对比。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode helper = dummy, cur = dummy; // cur.next is the node to be inserted
ListNode pre = dummy; // insert between pre and pre.next;
while (cur != null && cur.next != null) {
int val = cur.next.val;
while (pre.next.val < val) {
pre = pre.next;
}
if (pre != cur) {
ListNode tmp = pre.next; // insert
pre.next = new ListNode(val);
pre.next.next = tmp;
cur.next = cur.next.next;
} else {
cur = cur.next;
}
pre = dummy;
}
return dummy.next;
}
}
