删除排序数组中的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。
说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以”引用”方式传递的。也就是说,不对实参做任何拷贝

int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。

// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。

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

print(nums[i]);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int RemoveDuplicates(int[] nums) {
if(nums.Length == 0) return 0;
int index = 0;
for(int i = 0; i < nums.Length; i++)
{
if(nums[index] != nums[i])
{
nums[++index] = nums[i];
}
}
return index + 1;
}
}

买卖股票的最佳时机Ⅱ

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]

输出: 4

解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。

因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int MaxProfit(int[] prices)
{
int buy = -1;
int res = 0;
for(int i = 0; i < prices.Length - 1; i++)
{
if(i == buy) continue;
if( prices[i] < prices[i + 1])
{
buy = i;
res += prices[i + 1] - prices[buy];
}
}
return res;
}
}

旋转数组

旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右旋转 1 步: [7,1,2,3,4,5,6]

向右旋转 2 步: [6,7,1,2,3,4,5]

向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2

输出: [3,99,-1,-100]

解释:

向右旋转 1 步: [99,-1,-100,3]

向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。

要求使用空间复杂度为 O(1) 的 原地 算法。

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
// 暴力法
public class Solution {
public void Rotate(int[] nums, int k)
{
int temp, previous;
for (int i = 0; i < k; i++)
{
previous = nums[nums.Length - 1];
for(int j = 0; j < nums.Length; j++)
{
temp = nums[j];
nums[j] = previous;
previous = temp;
}
}
}
}
// 用新数组拷贝
public class Solution {
public void Rotate(int[] nums, int k)
{
int[] a = new int[nums.Length];
for(int i = 0; i < nums.Length; i++)
{
a[(i + k) % nums.Length] = nums[i];
}
for(int i = 0; i < nums.Length; i++)
{
nums[i] = a[i];
}
}
}
// 三次旋转
public class Solution {
public void Rotate(int[] nums, int k)
{
k %= nums.Length;
reverse(nums, 0, nums.Length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.Length - 1);

}
public void reverse(int[] nums, int start, int end)
{
while(start < end)
{
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start ++;
end --;
}
}
}

存在重复

给定一个整数数组,判断是否存在重复元素。

如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

示例 1:

输入: [1,2,3,1]

输出: true

示例 2:

输入: [1,2,3,4]

输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]

输出: true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 哈希表
public class Solution {
public bool ContainsDuplicate(int[] nums)
{
if(nums.Length <= 1) return false;
Hashtable h = new Hashtable();
for(int i = 0; i < nums.Length;i++)
{
if(h.ContainsKey(nums[i])) return true;
else h.Add(nums[i], i);
}
return false;
}
}
// 朴素(超时)
public class Solution {
public bool ContainsDuplicate(int[] nums)
{
for (int i = 0; i < nums.Length; i++)
for (int j = 0; j < i; j++)
if (nums[j] == nums[i]) return true;
return false;
}
}

只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

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
// 哈希集:HashSet只接受不重复的集合(占用了额外空间)
public class Solution {
public int SingleNumber(int[] nums) {
HashSet<int> s = new HashSet<int>();
for(int i = 0; i < nums.Length; i++)
{
if(!s.Add(nums[i]))
s.Remove(nums[i]);
}
return s.First();
}
}

// 逻辑方法:按位异或(xor)
// 1. 当一个数与0进行按位异或操作时,所得的为该值
// 2. 当相同的两个值进行异或时,所得为0
// 3. 因此,数组遍历时,result的值会在nums[i]和0之间变化
// 4. 两个相同的数经过这个过程后,会抵消。而只有一个的会被保留下来(即1)
public class Solution {
public int SingleNumber(int[] nums) {
int result = 0;
for(int i = 0; i < nums.Length; i++)
{
result ^= nums[i];
}
return result;
}
}

两个数组的交集Ⅱ

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]

输出: [2,2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出: [4,9]

说明:

输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。

我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢?你将如何优化你的算法?

  • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?

  • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 先排序,后遍历,双指针
public class Solution {
public int[] Intersect(int[] nums1, int[] nums2)
{
Array.Sort(nums1);
Array.Sort(nums2);
var res = new List<int>();
int i = 0;
int j = 0;
while(i < nums1.Length && j < nums2.Length)
{
if(nums1[i] == nums2[j])
{
res.Add(nums1[i]);
i++;
j++;
}
else if(nums1[i] < nums2[j])
{
i++;
}
else
{
j++;
}
}
return res.ToArray();
}
}

// 哈希表做法
public class Solution {
public int[] Intersect(int[] nums1, int[] nums2)
{
if(nums1 == null || nums2 == null || nums1.Length == 0 || nums2.Length == 0)
{
return new int[]{};
}
// 直接将nums1调整为小数组
if(nums2.Length < nums1.Length)
{
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
// 存下nums1所有不重复的元素,并记录出现次数
Dictionary<int, int> dic = new Dictionary<int, int>();
for(int i = 0; i < nums1.Length; i++)
{
if(!dic.ContainsKey(nums1[i]))
{
dic.Add(nums1[i],0);
}
else
{
dic[nums1[i]]++;
}
}
// 存nums2中含有nums1中的元素到结果
var res = new List<int>();
for(int i = 0; i < nums2.Length; i++)
{
if(dic.ContainsKey(nums2[i]) && dic[nums2[i]] >= 0)
{
res.Add(nums2[i]);
dic[nums2[i]]--;
}
}
return res.ToArray();
}
}

/*
------------------------
进阶三问
------------------------
1. 即解1,直接按照这个双指针思路查找即可。时间复杂度O(n),空间复杂度O(1)。
2. 即解2,将较小的数组哈希计数,随后在另一个数组中根据哈希来寻找。时间复杂度O(max(n, m)) 空间复杂度O(min(n, m))。
3. 内存小,要求用原地算法。需要空间复杂度最小的解1。解1需要改造,用归并排序?

*/