LeetCode演算法題-K-diff Pairs in an Array(Java實現)
這是悅樂書的第254 次更新,第267 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第121題(順位題號是532)。給定一個整數陣列和一個整數k,您需要找到陣列中唯一的k-diff對的數量。 這裡k-diff對被定義為整數對(i,j),其中i和j都是陣列中的數字,它們的絕對差是k。例如:
輸入:[3,1,4,1,5],k = 2
輸出:2
說明:陣列中有兩個2-diff對,(1,3)和(3,5)。雖然我們在輸入中有兩個1,但我們應該只返回唯一對的數量。
輸入:[1,2,3,4,5],k = 1
輸出:4
說明:陣列中有四個1-diff對,(1,2),(2,3),(3,4)和(4,5)。
輸入:[1,3,1,5,4],k = 0
輸出:1
說明:陣列中有一個0-diff對,(1,1)。
注意:
-
對(i,j)和(j,i)計為同一對。
-
陣列的長度不會超過10,000。
-
給定輸入中的所有整數都屬於以下範圍:[-1e7, 1e7]。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
暴力解法。先排序,然後使用兩層迴圈,計算不同元素的絕對值,如果等於k,次數就加1。在外面第一層迴圈那裡,如果前後元素相同,就跳過當前迴圈,進行下一次迴圈。在內層迴圈那裡同樣做了類似的判斷,排除重複計算。
此解法的時間複雜度是O(n^2),空間複雜度是O(1)。
public int findPairs(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Arrays.sort(nums); int count = 0; for (int i=0; i<nums.length; i++) { int n = nums[i]; if (i >= 1 && nums[i-1] == nums[i]) { continue; } for (int j=i+1; j<nums.length; j++) { if (j >= i+2 && nums[j-1] == nums[j]) { continue; } if (Math.abs(n - nums[j]) == k) { count++; } } } return count; }
03 第二種解法
第一種解法時間複雜度太高了,得降低點。第一種解法,我們是做減法,求絕對值,來判斷是否等於k,我們也可以做加法,拿當前元素加上k,然後看新元素是否存在於陣列中。同時還要考慮重複的計算資料,因此參與計算的元素是唯一的,對此我們可以使用HashMap,已元素值作為key,該元素值出現次數為value。遍歷key,如果key加上k後的值存在於map中,次數加1,另外如果k為0的時候,只需要判斷每個key所對應的value是否大於等於2即可。
此解法的時間複雜度是O(n),最壞情況也可能是O(n^2),空間複雜度是O(n)。
public int findPairs2(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for (int n : nums) { map.put(n, map.getOrDefault(n, 0)+1); } int count = 0; if (k == 0) { for (Integer key: map.keySet()) { if (map.get(key) >= 2) { count++; } } } else { for (Integer key: map.keySet()) { if (map.containsKey(key+k)) { count++; } } } return count; }
04 第三種解法
對於第二種解法,還可以將判斷放在迴圈體裡面。
public int findPairs3(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for (int n : nums) { map.put(n, map.getOrDefault(n, 0)+1); } int count = 0; for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (k == 0) { if (entry.getValue() >= 2) { count++; } } else { if (map.containsKey(entry.getKey()+k)) { count++; } } } return count; }
05 第四種解法
使用HashSet。使用兩個HashSet,同樣分為兩種情況:k等於0和K不等於0。
如果k等於0時,對陣列進行遍歷,如果當前元素不存在於set1中,就新增進set1,如果存在set1中,就去判斷是否存在於set2中,如果不存在,次數就加1,並將元素新增進set2中。
如果k不等於0,遍歷陣列,將當前元素新增進set1,將當前元素加上k後再新增進set2,然後使用retainAll方法,將set1中不包含set2元素的元素剔除掉(也就是兩set的交集),最後count等於set1中元素的個數。
public int findPairs4(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); int count = 0; if (k == 0) { for (int n : nums) { if (!set1.contains(n)) { set1.add(n); } else { if (!set2.contains(n)){ count++; } set2.add(n); } } } else { for (int n : nums) { set1.add(n); set2.add(n + k); } set1.retainAll(set2); count = set1.size(); } return count; }
06 第五種解法
使用雙指標。還是先將資料排序,定義左右兩個指標,分別從0開始,如果左右指標相等,說明是迴圈的第一次或者重複了,就需要將右指標往後移動一位。如果左指標所指向元素加上k後等於右指標的元素,那麼次數加1,接著要判斷,如果右指標所指向位置後面的元素和當前元素相等,那麼右指標繼續往後移動。如果左指標所指向元素加上k後小於右指標的元素,說明左邊的元素小了,左指標向前移動。如果左指標所指向元素加上k後大於右指標的元素,說明右邊的元素小了,右指標向前移動。
此解法的時間複雜度是O(n log(n)),空間複雜度是O(1)。
public int findPairs5(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Arrays.sort(nums); int count = 0; int start = 0, end = 0; while (end < nums.length) { if (start == end) { end++; } else if (nums[start] + k == nums[end]) { count++; while (end + 1 < nums.length && nums[end] == nums[end + 1]) { end++; } end++; } else if (nums[start] + k < nums[end]) { start++; } else if (nums[start] + k > nums[end]) { end++; } } return count; }
07 小結
此題的測試用例中,k出現了負值,所以在特殊情況判斷中,還需要判斷k小於0,這也是本題不嚴謹的一個地方。
演算法專題目前已日更超過三個月 ,演算法題文章121 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!