資訊專(zhuān)欄INFORMATION COLUMN
摘要：代碼集合法復(fù)雜度時(shí)間空間思路同樣使用集合，但這次我們要維護(hù)集合的大小不超過(guò)，相當(dāng)于是記錄一個(gè)寬度為的窗口中出現(xiàn)過(guò)的數(shù)字。
Contains Duplicate I
集合法 復(fù)雜度Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
時(shí)間 O(N) 空間 O(N)
思路用一個(gè)集合記錄之前遇到過(guò)的數(shù)字，如果新的數(shù)字已經(jīng)在集合中出現(xiàn)過(guò)了，則說(shuō)明有重復(fù)。
代碼public class Solution {
public boolean containsDuplicate(int[] nums) {
Set set = new HashSet();
for(int i = 0; i < nums.length; i++){
if(set.contains(nums[i])) return true;
set.add(nums[i]);
}
return false;
}
}
Contains Duplicate II
集合法 復(fù)雜度Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
時(shí)間 O(N) 空間 O(K)
思路同樣使用集合，但這次我們要維護(hù)集合的大小不超過(guò)k，相當(dāng)于是記錄一個(gè)寬度為k的窗口中出現(xiàn)過(guò)的數(shù)字。
代碼public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set set = new HashSet();
for(int i = 0; i < nums.length; i++){
if(set.contains(nums[i])) return true;
set.add(nums[i]);
if(set.size()>k) set.remove(nums[i-k]);
}
return false;
}
}
Contains Duplicate III
二叉搜索樹(shù) 復(fù)雜度Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
時(shí)間 O(NlogK) 空間 O(K)
思路要求判斷之前是否存在差值小于t的數(shù)字，我們需要知道在當(dāng)前數(shù)字x兩邊的數(shù)字，即最大的小于x的數(shù)字和最小的大于x的數(shù)字。二叉搜索樹(shù)有也有這樣的性質(zhì)，它的左子樹(shù)的最右節(jié)點(diǎn)是最大的較小值，右子樹(shù)的最左節(jié)點(diǎn)是最小的較大值。這里我們用TreeSet這個(gè)類(lèi)，它實(shí)現(xiàn)了紅黑樹(shù)，并有集合的性質(zhì)，非常適合這題。我們同樣也是維護(hù)一個(gè)大小為k的TreeSet，多余k個(gè)元素時(shí)把最早加入的給刪除。用ceiling()和floor()可以找到最小的較大值和最大的較小值。
代碼public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet set = new TreeSet();
for(int i = 0; i < nums.length; i++){
int x = nums[i];
// 最大的小于x的數(shù)字
if(set.ceiling(x) != null && set.ceiling(x) <= t + x) return true;
// 最小的大于x的數(shù)字
if(set.floor(x) != null && x <= t + set.floor(x)) return true;
set.add(x);
if(set.size()>k) set.remove(nums[i-k]);
}
return false;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64497.html
摘要：輸入一個(gè)整數(shù)數(shù)組，查看數(shù)組中是否存在重復(fù)的值。新的數(shù)組中數(shù)組的下標(biāo)為原數(shù)組的值，如果遍歷過(guò)，則設(shè)置為。這里使用了作為實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)堆的形式對(duì)集合中的數(shù)據(jù)進(jìn)行存儲(chǔ)，從而我們可以通過(guò)某種順序獲得該集合中的所有順序。 217 Contains Duplicate Given an array of integers, find if the array contains any dup...
摘要：題目詳情輸入一個(gè)整數(shù)的數(shù)組，如果數(shù)組中的元素有重復(fù)的，那么返回，如果數(shù)組中的元素都是唯一的，那么返回思路這道題理解起來(lái)比較簡(jiǎn)單，首先還是要注意一下邊界條件異常輸入，對(duì)于長(zhǎng)度小于等于的數(shù)組做一個(gè)直接的返回對(duì)于這種要考慮數(shù)組中元素的重復(fù)的問(wèn)題， 題目詳情 Given an array of integers, find if the array contains any duplicate...
摘要：題目鏈接題目分析返回給定的數(shù)組中是否有元素重復(fù)出現(xiàn)。思路用和即可最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D90 217. Contains Duplicate 題目鏈接 217. Contains Duplicate 題目分析 返回給定的數(shù)組中是否有元素重復(fù)出現(xiàn)。 思路 用count和array_unique即可 最終代碼
Contains Duplicate Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false ...
Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...
閱讀 2026·2021-11-24 09:39
閱讀 1168·2021-09-10 11:25
閱讀 1798·2021-09-08 10:42
閱讀 3760·2021-09-06 15:00
閱讀 2514·2019-08-30 15:54
閱讀 3128·2019-08-29 17:08
閱讀 3288·2019-08-29 11:26
閱讀 2850·2019-08-28 18:27
