FilesExpand file tree

 master

/

Program.cs

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (54 loc) · 1.36 KB

 master

/

Program.cs

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (54 loc) · 1.36 KB

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

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Q53_02_MissingNumber

{

class Program

{

static void Main(string[] args)

{

int[] a = {0, 1, 3};

Solution s= new Solution();

int v= s.MissingNumber(a);

}

}

/// <summary>

/// 时间复杂度：O(logn)

/// 空间复杂度：O(1)

/// </summary>

public class Solution

{

public int MissingNumber(int[] nums)

{

if (nums.Length <= 0)

{

return 0;

}

int leftIndex = 0;

int rightIndex = nums.Length - 1;

while (leftIndex <= rightIndex)

{

int midIndex = (leftIndex + rightIndex) >> 1;

if (nums[midIndex] != midIndex)

{

if (midIndex == 0 || nums[midIndex - 1] == (midIndex - 1))

{

return midIndex;

}

rightIndex = midIndex - 1;

}

else

{

leftIndex = midIndex + 1;

}

}

if (leftIndex == nums.Length)

{

return nums.Length;

}

return -1;

}

}

}