本文共 5920 字,大约阅读时间需要 19 分钟。
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.public void merge(int A[], int m, int B[], int n) { //参数合法性校验 if(A == null || A.length < 1 || B == null || B.length < 1) return; //两个数组的元素总个数 int len = m + n - 1; //A数组元素的下标(从后向前) int i = m - 1; //B数组元素的下标(从后向前) int j = n - 1; //循环向前比较并排序 while(i >= 0 && j >= 0){ A[len--] = A[i] >= B[j] ? A[i--] : B[j--]; } //A数组中元素有剩余 while(i >= 0){ A[len--] = A[i--]; } //B数组中元素有剩余 while(j >= 0){ A[len--] = B[j--]; } }
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //边界值检测 if(l1 == null) return l2; if(l2 == null) return l1; //返回链表的头结点 ListNode head = null; //中间节点用于连接下一节点 ListNode temp = null; //依次向后比较节点 while(l1 != null && l2 != null){ if(head == null){ if(l1.val <= l2.val){ head = l1; l1 = l1.next; }else{ head = l2; l2 = l2.next; } temp = head; }else{ if(l1.val <= l2.val){ temp.next = l1; temp = temp.next; l1 = l1.next; }else{ temp.next = l2; temp = temp.next; l2 = l2.next; } } } //链接剩余节点 temp.next = l1 != null ? l1 : l2; return head; }
方法一:使用归并排序
//使用归并排序 public ListNode mergeKLists(ArrayListlists) { //边界值检测 if(lists == null || lists.size() == 0) return null; //调用归并方法 return mergeCore(lists,0,lists.size() - 1); } //归并处理K个链表的合并 private ListNode mergeCore(ArrayList list,int begin,int end){ if(begin == end) return list.get(begin); if(begin > end) return null; int mid = (begin + end) / 2; ListNode left = mergeCore(list,begin,mid); ListNode right = mergeCore(list,mid+1,end); return merge(left,right); } //合并两个链表 private ListNode merge(ListNode l1,ListNode l2){ //边界值检测 if(l1 == null) return l2; if(l2 == null) return l1; //返回链表的头结点 ListNode head = null; //中间节点用于连接下一节点 ListNode temp = null; //依次向后比较节点 while(l1 != null && l2 != null){ if(head == null){ if(l1.val <= l2.val){ head = l1; l1 = l1.next; }else{ head = l2; l2 = l2.next; } temp = head; }else{ if(l1.val <= l2.val){ temp.next = l1; temp = temp.next; l1 = l1.next; }else{ temp.next = l2; temp = temp.next; l2 = l2.next; } } } //链接剩余节点 temp.next = l1 != null ? l1 : l2; return head; }
方法二:使用优先队列(堆排序)
For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.//利用数组下标与数组元素之间的关系将数组元素位置进行调整 public int firstMissingPositive(int[] A) { //输入参数合法性校验 if(A == null) return 0; //当数组中没有元素时,应该返回第一个正整数 if(A.length < 1) return 1; //循环处理每一个数组元素,按照数组元素与下标的对应关系进行调整 for(int i = 0 ; i < A.length ; i++){ //一定要使用循环保证当前位置的元素为负数,或者已经与当前下标正确对应 while(A[i] > 0 && A[i] != i+1){ if(A[i]-1 >= A.length){ break; } if(A[i] == A[A[i]-1]) break; int temp = A[i]; A[i] = A[A[i]-1]; A[temp-1] = temp; } } //循环判断每一个元素是否与当前数组下标对应 for(int i = 0 ; i < A.length ; i++){ if(A[i] != i+1) return i+1; } //如果每一个数组元素都与下标对应关系正确,那么就返回最后一个数组元素的下一个整数 return A.length+1; }
public void sortColors(int[] A) { if(A == null || A.length <= 1) return; int zeroIndex = 0; int twoIndex = A.length - 1; for(int i = 0 ; i < A.length ; i++){ while(i < twoIndex && A[i] == 2){ swap(A,i,twoIndex); twoIndex--; } while(i > zeroIndex && A[i] == 0){ swap(A,i,zeroIndex); zeroIndex++; } if(i == twoIndex) return; } } private void swap(int[] A,int i,int j){ A[i] = A[i] + A[j]; A[j] = A[i] - A[j]; A[i] = A[i] - A[j]; }
转载地址:http://lxsvb.baihongyu.com/