题目链接:
目录
- 暴力解法 (超时)
- 优化内层查找 (On - > O1 但超时)
- 优化重复迭代:在值域而非定义域迭代,去重 (超时)
- 优化空迭代:HashSet去重,每次迭代的元素都存在 (26ms)
- 从左边界重复入手再优化:HashMap存右界解法 (27ms)
- 另解:排序+链式判断(26ms)
暴力解法 (超时)
class Solution {
public int longestConsecutive(int[] nums) {
int n = nums.length;
int ans = 0;
// 遍历数组中的每个元素num
for (int i = 0; i < n; i++) {
// 以num为起点,每次+1向后遍历num+1,num+2,num+3...
int cur = nums[i] + 1;
while (true) {
// 标识是否在数组中找到了cur
boolean flag = false;
// 在数组中找cur
for (int j = 0; j < n; j++) {
if (nums[j] == cur) {
flag = true;
break;
}
}
if (!flag) {
break;
}
cur ++;
}
ans = Math.max(ans, cur - nums[i]);
}
return ans;
}
}
优化内层查找 (On - > O1 但超时)
class Solution {
Map<Integer, Integer> map;
public int longestConsecutive(int[] nums) {
map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
map.putIfAbsent(nums[i], 1);
}
int n = nums.length;
int ans = 0;
// 遍历数组中的每个元素num
for (int i = 0; i < n; i++) {
// 以num为起点,每次+1向后遍历num+1,num+2,num+3...
int cur = nums[i] + 1;
while (map.containsKey(cur)) {
cur ++;
}
ans = Math.max(ans, cur - nums[i]);
}
return ans;
}
}
问题:重复的边界会重新迭代
优化重复迭代:在值域而非定义域迭代,去重 (超时)
class Solution {
public int longestConsecutive(int[] nums) {
int min = 0x3f3f3f3f, max = -0x3f3f3f3f;
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
map.putIfAbsent(nums[i], 1);
if(min > nums[i]) min = nums[i];
if(max < nums[i]) max = nums[i];
}
int ans = 0;
for (int i = min; i <= max; i++) {
int cur = i;
while (map.containsKey(cur)) {
cur ++;
}
ans = Math.max(ans, cur - i);//nums[i]);
i = cur;
}
return ans;
}
}
问题:值域大且元素离散度大时,会大量迭代到不存在的元素,空迭代
优化空迭代:HashSet去重,每次迭代的元素都存在 (26ms)
class Solution {
public int longestConsecutive(int[] nums) {
int ans = 0, n = nums.length;
Set<Integer> set = new HashSet<>(128);
for(int i = 0; i < n; i++) set.add(nums[i]);
for(Integer k : set) {
int cur = k;
if(set.contains(k - 1)) continue;
while (set.contains(cur)) {
cur ++;
} ans = Math.max(ans, cur - k);
} return ans;
}
}
从左边界重复入手再优化:HashMap存右界解法 (27ms)
class Solution {
public int longestConsecutive(int[] nums) {
int ans = 0, n = nums.length;
Map<Integer, Integer> map = new HashMap<>(128);
for(int i = 0; i < n; i++)
map.putIfAbsent(nums[i], nums[i]);
for(int num : nums) {
if(map.containsKey(num - 1)) continue;
int rgt = map.get(num);
if(rgt != num) continue;
while(map.containsKey(rgt)){
rgt++;
} map.put(num, rgt);
ans = Math.max(ans, rgt - num);
} return ans;
}
}
另解:排序+链式判断(26ms)
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0) return 0;
int ans = 0, cur = 0;
// Arrays.sort(nums);
sort(nums);
for(int i = 1; i < nums.length; i++){
// System.out.println(nums[i] - nums[i - 1]);
int dif = nums[i] - nums[i - 1];
if(dif == 0) continue;
else if(dif == 1) ++cur;
else {
ans = Math.max(ans, cur + 1);
cur = 0;
}
}
ans = Math.max(ans, cur + 1);
return ans;
}
void sort(int [] nums){
int [] tmp = new int[nums.length];
dfs(nums, tmp, 0, nums.length - 1);
}
void dfs(int [] nums, int [] tmp, int lft, int rgt){
if(lft >= rgt) return;
int mid = (lft + rgt) >> 1;
dfs(nums, tmp, lft, mid);
dfs(nums, tmp, mid + 1, rgt);
int i = lft, j = mid + 1, p = 0;
while(i <= mid && j <= rgt)
tmp[p++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
while(i <= mid) tmp[p++] = nums[i++];
while(j <= rgt) tmp[p++] = nums[j++];
for(int u = 0; u < p; u++){
nums[u + lft] = tmp[u];
}
}
}
标签:01,cur,nums,int,++,算法,num,ans,刷题
From: https://www.cnblogs.com/luoyicode/p/17683098.html