leetcode — first-missing-positive
2024-09-19 19:52:29
/**
*
* Source : https://oj.leetcode.com/problems/first-missing-positive/
*
* Created by lverpeng on 2017/7/15.
*
* 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.
*
* Your algorithm should run in O(n) time and uses constant space.
*
*/
public class FindFirstMissingPositive {
/**
* 找到第一个确实的正整数
* 题目特点：
* 数组是一个整数数组
* 数组中的正整数中除了缺失的一个正整数，其他都是连续的，也就是说一个长度为n的数组，数组中的数是1-n（最多，因为可能有0或者负数）
*
* 可以把每一个数房放在其下标减1的位置
* 然后遍历数组，发现num[i] != num[i-1]或说明就找到了缺失的数
*
* @param num
* @return
*/
public int fistMissingPositive (int[] num) {
for (int i = 0; i < num.length;) {
if (num[i] > 0 && num[i] != num[num[i] - 1]) {
int temp = num[num[i]-1];
num[num[i]-1] = num[i];
num[i] = temp;
} else {
i ++;
}
}
for (int i = 1; i < num.length; i++) {
if (num[i] != (num[i-1] + 1)) {
return num[i - 1] + 1;
}
}
return -1;
}
public static void main(String[] args) {
FindFirstMissingPositive findFirstMissingPositive = new FindFirstMissingPositive();
int[] arr = new int[]{1,2,0};
int[] arr1 = new int[]{3,4,-1,1};
int[] arr2 = new int[]{3,4,1,1};
int[] arr3 = new int[]{3,4,1,1};
System.out.println(findFirstMissingPositive.fistMissingPositive(arr));
System.out.println(findFirstMissingPositive.fistMissingPositive(arr1));
System.out.println(findFirstMissingPositive.fistMissingPositive(arr2));
System.out.println(findFirstMissingPositive.fistMissingPositive(arr3));
}
}
最新文章
- swift-懒加载
- 用帝国CMS时遇到的问题
- CF570D——Tree Requests
- UIPickerView 循环滚动（一种假象）
- jboss4.2.3禁用http put/delete等请求
- tornado框架之路一
- 常用shell笔记
- Vue + WebApi 小项目：构造自己的在线 Markdown 笔记本应用
- 关于memset赋值问题
- YOLO 从数据集制作到训练
- caffe调loss方法
- Dubbo 在maven项目中的应用
- XAMPP配置基于虚拟目录、多域名的环境
- memcmp 和 memcpy使用
- phalcon分页的处理
- iOS- 如何将应用集成发短信、发邮件、打电话
- Python WebDriver 文件上传（二）
- Javascript深入__proto__和prototype的区别和联系
- Visual Studio - 安装VAX
- 通过SSRS创建动态分组报表的方法！