128. 最长连续序列
import java.util.*;
public class Test {
public static void main(String[] args) {
int[] nums = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
int res = new Solution().longestConsecutive(nums);
System.out.println(res);
}
}
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
//数组转set集合,可以去重(连续序列重复的数字不算)
Set<Integer> numsSet = new HashSet<>();
for (int num : nums) {
numsSet.add(num);
}
int longest = 0;
for (Integer item : numsSet) {//set集合也可以遍历
int length = 0;
//若item-1不在set集合中,则item就是连续序列的第一个元素
if (!numsSet.contains(item - 1)) {
length++;
//尝试扩展以item开头的连续序列
while (numsSet.contains(item + 1)) {
length++;
item++;
}
}
longest = Math.max(longest, length);
}
return longest;
}
}
由于每个数字只会被遍历一次(无论是添加到HashSet中还是作为序列的起点被检查),所以整个算法的时间复杂度仍然是O(n)。
283. 移动零
用一个指针指到数组开头。从头开始遍历数组,看到不为 0 的数就 copy 到指针指向的位置,每 copy 完一个,指针就后移一个位置。
class Solution {
public void moveZeroes(int[] nums) {
int flag = 0;
for(int i=0; i<nums.length; i++){
if(nums[i]!=0){
nums[flag] = nums[i];
flag++;
}
}
for(int i=flag; i<nums.length; i++){
nums[i]=0;
}
}
}