`
hcx2013
  • 浏览: 82118 次
社区版块
存档分类
最新评论

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.

Your algorithm should run in O(n) time and uses constant space.

 

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
        	if (nums[left] == left + 1) {
        		left++;
        	} else if (nums[left] <= left || nums[left] > right || nums[left] == nums[nums[left]-1]) {
        		nums[left] = nums[--right];
        	} else {
        		swap(nums, left, nums[left]-1);
        	}
        }
        return left + 1;
    }

	private void swap(int[] nums, int i, int j) {
		// TODO Auto-generated method stub
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
}

 

 

5
2
分享到:
评论

相关推荐

    cpp-算法精粹

    First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 查找 Search for a Range Search Insert Position Search in Rotated Sorted Array Search in Rotated Sorted Array II ...

    lrucacheleetcode-leetcode:leetcode

    First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain Water 85...

    LeetCode最全代码

    268| [Missing Number](https://leetcode.com/problems/missing-number/) | [C++](./C++/missing-number.cpp) [Python](./Python/missing-number.py) | _O(n)_ | _O(1)_ | Medium | LintCode || 318| [Maximum ...

    Leetcode-Solutions:JavaScript 语言的 Leetcode 解决方案

    ├── First Missing Positive │ ├── Readme.md │ └── solution.js ├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── ...

    leetcode打不开-leetcode:leetcode

    leetcode打不开Leetcode Note Tips Tip1: Two pointer for sorted array (#Array 1. Two Sum) Tip2: Sum[i:j] = Sum[0:j] - Sum[0:i] for continuous array (# Array 560. ...First Missing Positive

    leetcode71python-leetcode:leetcode

    leetcode 71 Python用 ...Missing Positive (HARD) leetcode 42. 收集雨水 (HARD) leetcode 44. 通配符匹配 (HARD) leetcode 45. Jump Game II (HARD) Leetcode 51. N-Queens (HARD) Leetcode 52. N-

    lrucacheleetcode-oh-my-leetcode:Leetcode题解

    题:**First Missing Positive 给定一个未排序的整数数组,找到第一个缺失的正整数。 例如,给定 [1,2,0] 返回 3,而 [3,4,-1,1] 返回 2。 您的算法应该在 O(n) 时间内运行并使用恒定空间。 **第 0003 题:**String ...

    Positive approximation and converse approximation in interval-valued fuzzy rough sets

    Methods of fuzzy rule extraction based on rough set theory are rarely ... The data completeness of missing attribute values is first presented.Positive and converse approximations in interval-valued fuzz

    收集面试中提出的一些重要问题。-C/C++开发

    收集面试中提出的一些重要问题。 数据结构算法面试问题面试中提出的一些重要问题的集合。 数组...missing-positive / https://leetcode.com/problems/container-with-most-water/ htt

    leetcode2-code_interview:LeetCodeLintCode题解,剑指offer题目,互联网公司面试,BAT外企等面试题

    leetcode 2 code_interview leetcode和lintcode的一些题目的解法 是剑指offer 是面试中遇到的有意思的题目总结,比如说BAT,intel,NVIDIA等公司面试的题目记录 ...41-first-missing-positive 01-Two-Sum 求解第K

    股票买卖最佳时机leetcode-Java-Projects:Java项目和面试问题的存储库,用于编码面试的练习

    股票买卖最佳时机leetcode Java项目 这是 ...First_Missing_Positive Generate_All_Parenthesis_2 实现_StrStr Largest_Distance_Between_Nodes_Of_A_Tree Largest_Rectangle_In_Histogram Least_C

    gasstationleetcode-LeetCode_Practice:我的LeetCode练习从2020年开始

    41_First_Missing_Positive 299_Bulls_and_Cows 134_Gas_Station 118_Pascal's_Triangle_I 119_Pascal's_Triangle_II 169_Majority_Element 229_Majority_Element_II 274_H_索引 275_H_Index_II 217_Contain_...

    leetcode跳跃-leetcode:leetcode解题之路

    缺失的第一个整数](./Array/first-missing-positive.md) [0042 接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists....

    eac3to V3.17

    * fixed: positive edit began a bit too early * fixed: two ID3 tags after each other made eac3to fail detecting the format * fixed: some VOB files were not detected properly v2.87 * fixed: negative ...

    EurekaLog_7.5.0.0_Enterprise

    13)..Added: "User" and "Session" columns to processes list, processes list is also sorted by session first 14)..Added: Support for showing current user processes only 15)..Added: Expanding environment...

    一个win32下的ARM开源编译器

    FASMARM v1.42 This package is an ARM assembler add-on for FASM. FASMARM currently supports the full range of instructions for 32-bit and 64-bit ARM processors and coprocessors up to and including v8...

    四级英语真题

    The ideal lecturer is one who has an interesting teaching style, a diverse academic background, and a good reputation among students. &lt;br&gt; There are both positive and negative aspects to allowing ...

    数位板压力测试

    sdk LCS/Telegraphics Wintab* Interface Specification 1.1: 16- and 32-bit API Reference ... The coordinate system will be right-handed, that is, the positive x axis points from left to right, and the ...

Global site tag (gtag.js) - Google Analytics