FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

《剑指offer(第2版)》 >>> 面试题53：在排序数组中查找数字 题目三：数组中数值和下标相等的元素 · apple006/java-code@5e41b44 · GitHub

  1. apple006
  2. java-code

Repository navigation

Commit 5e41b44

Browse files
xdc0209
committed
《剑指offer(第2版)》 >>> 面试题53：在排序数组中查找数字 题目三：数组中数值和下标相等的元素
1 parent f95bcb4 commit 5e41b44

3 files changed

Lines changed: 136 additions & 0 deletions

File tree

‎basicKnowledge/src/com/xdc/basic/algorithm/sword4offer/question53/Solution.java‎

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,9 @@
22

33
public class Solution
44
{
5+
/**
6+
* 面试题53：在排序数组中查找数字 题目一：数字在排序数组中出现的次数。
7+
*/
58
public static int GetNumberOfK(int[] array, int k)
69
{
710
if (array == null || array.length == 0)
@@ -63,9 +66,134 @@ else if (array[mid] < k)
6366
}
6467
}
6568

69+
/**
70+
* 面试题53：在排序数组中查找数字 题目二：0~n-1中缺失的数字。
71+
* 使用异或，时间复杂度O(n)，空间复杂度O(1)。
72+
*/
73+
public static int GetMissingNumber(int[] array)
74+
{
75+
if (array == null || array.length == 0)
76+
{
77+
return 0;
78+
}
79+
80+
int ans = 0;
81+
82+
for (int i = 0; i < array.length; i++)
83+
{
84+
ans = ans ^ array[i];
85+
}
86+
87+
for (int i = 0; i <= array.length; i++)
88+
{
89+
ans = ans ^ i;
90+
}
91+
92+
return ans;
93+
}
94+
95+
/**
96+
* 面试题53：在排序数组中查找数字 题目二：0~n-1中缺失的数字。
97+
* 使用求和(容易溢出)，时间复杂度O(n)，空间复杂度O(1)。
98+
*/
99+
public static int GetMissingNumber2(int[] array)
100+
{
101+
if (array == null || array.length == 0)
102+
{
103+
return 0;
104+
}
105+
106+
int ans = 0;
107+
108+
for (int i = 0; i <= array.length; i++)
109+
{
110+
ans = ans + i;
111+
}
112+
113+
for (int i = 0; i < array.length; i++)
114+
{
115+
ans = ans - array[i];
116+
}
117+
118+
return ans;
119+
}
120+
121+
/**
122+
* 面试题53：在排序数组中查找数字 题目二：0~n-1中缺失的数字。
123+
* 使用二分查找，时间复杂度O(logn)，空间复杂度O(1)。
124+
*/
125+
public static int GetMissingNumber3(int[] array)
126+
{
127+
if (array == null || array.length == 0)
128+
{
129+
return 0;
130+
}
131+
132+
int low = 0;
133+
int high = array.length - 1;
134+
int missing = -1;
135+
while (low <= high)
136+
{
137+
int mid = (low + high) / 2;
138+
139+
if (array[mid] != mid)
140+
{
141+
high = mid - 1;
142+
missing = mid;
143+
}
144+
else // array[mid] == mid
145+
{
146+
low = mid + 1;
147+
}
148+
}
149+
150+
return missing;
151+
}
152+
153+
/**
154+
* 面试题53：在排序数组中查找数字 题目三：数组中数值和下标相等的元素。
155+
* 使用二分查找，时间复杂度O(logn)，空间复杂度O(1)。
156+
*/
157+
public static int GetNumberSameAsIndex(int[] array)
158+
{
159+
if (array == null || array.length == 0)
160+
{
161+
return -1;
162+
}
163+
164+
int low = 0;
165+
int high = array.length - 1;
166+
167+
while (low <= high)
168+
{
169+
int mid = (low + high) / 2;
170+
171+
if (array[mid] > mid)
172+
{
173+
high = mid - 1;
174+
}
175+
else if (array[mid] < mid)
176+
{
177+
low = mid + 1;
178+
}
179+
else // array[mid] == mid
180+
{
181+
return mid;
182+
}
183+
}
184+
185+
return -1;
186+
}
187+
66188
public static void main(String[] args)
67189
{
68190
System.out.println(GetNumberOfK(newArray(1, 2, 3, 3, 3, 3, 4, 5), 0));
191+
192+
System.out.println(GetMissingNumber(newArray(0, 1, 3, 4, 5, 6)));
193+
System.out.println(GetMissingNumber2(newArray(0, 1, 3, 4, 5, 6)));
194+
System.out.println(GetMissingNumber3(newArray(0, 1, 3, 4, 5, 6)));
195+
196+
System.out.println(GetNumberSameAsIndex(newArray(-3, -1, 1, 3, 5)));
69197
}
70198

71199
private static int[] newArray(int... values)

‎basicKnowledge/src/com/xdc/basic/algorithm/sword4offer/question53/面试题53：在排序数组中查找数字 题目三：数组中数值和下标相等的元素.txt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
摘自：《剑指offer(第2版)》 >>> 面试题53：在排序数组中查找数字 题目三：数组中数值和下标相等的元素
2+
3+
问题描述：
4+
假设一个单调递增的数组里边的每个元素都是整数并且是唯一的。请实现一个函数，找出数组中任意一个数值等于其下标的元素。例如在数组{-3，-1,1,3,5}中，数字3和它的下标相等。

‎basicKnowledge/src/com/xdc/basic/algorithm/sword4offer/question53/面试题53：在排序数组中查找数字 题目二：0~n-1中缺失的数字.txt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
摘自：《剑指offer(第2版)》 >>> 面试题53：在排序数组中查找数字 题目二：0~n-1中缺失的数字
2+
3+
问题描述：
4+
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。在范围0~n-1范围内的n个数字中有且只有一个数字不在该数组中，请找出该数字。

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL