首页 > 代码库 > in place swap 笔记
in place swap 笔记
First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
尝试下用两根指针进行调换排序，但是处理返回结果太麻烦
简单的方式是扫描一遍数组，当有misplace的数的时候，把它换到它相应的正确位置上去
1 public class Solution { 2 public int firstMissingPositive(int[] A) { 3 if (A == null) { 4 return 1; 5 } 6 for (int i = 0; i < A.length; i++) { 7 while (A[i] > 0 && A[i] <= A.length && A[i] != (i+1)) {//找到位置不正确的点和正确位置的点交换 8 int tmp = A[A[i]-1]; 9 if (tmp == A[i]) {10 break;11 }12 A[A[i]-1] = A[i];13 A[i] = tmp;14 }15 }16 17 for (int i = 0; i < A.length; i++) {18 if (A[i] != (i+1)) {19 return i + 1;20 }21 }22 return A.length + 1;23 }24 25 }
in place swap 笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。