FilesExpand file tree

 main

/

0041-first-missing-positive.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

31 lines (28 loc) · 787 Bytes

 main

/

0041-first-missing-positive.java

Copy path

Top

File metadata and controls

• Code
• Blame

31 lines (28 loc) · 787 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution {

public int firstMissingPositive(int[] nums) {

int n = nums.length, size = 0;

while(n > 0){

n = n>>1;

size++;

}

n = nums.length;

int pivot = 0;

for(int i = 0; i < n; i++){

if(nums[i] <= 0 || nums[i] > n){

int temp = nums[i];

nums[i] = nums[pivot];

nums[pivot] = temp;

pivot++;

}

}

for(int i= 0; i < pivot; i++)

nums[i] = 0;

for(int i= pivot; i < n; i++){

nums[(nums[i] - 1)&((1<<size) - 1)] |= (1<<size);

}

for(int i= 0; i < n; i++)

if((nums[i] & (1<<size)) == 0)

return i+1;

return n+1;

}

}