[LintCode] K-diff Pairs in an Array

Leck1e 發布于2019-08-15 18:16 / 1220人閱讀

Problem

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example

Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Solution

public class Solution {
    /**
     * @param nums: an array of integers
     * @param k: an integer
     * @return: the number of unique k-diff pairs
     */
    public int findPairs(int[] nums, int k) {
        //it actually wants unique pairs, so need to sort and leave out the duplicates
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length-1; i++) {
            if (i != 0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < nums.length; j++) {
                if (j != i+1 && nums[j] == nums[j-1]) continue;
                if (nums[j] - nums[i] == k) count++;
            }
        }
        return count;
    }
}

云服務器 GPU云服務器 in_array() in_array in_array()函數 in_array()示例代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69719.html

leetcoed 532 K-diff Pairs in an Array

摘要：由于無法處理相同的操作，所依對于的時候，我采用了進行操作。為時，對于每一次遍歷，找到這個值是否已經存在在里，同時獲取這個值出現過的次數。題目詳情 Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-d...

SimpleTriangle 2019-08-15 13:53 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
[LintCode] Reverse Pairs

摘要：暴力解法就是時靈時不靈，兩次一次。希望看到的大神能夠分享優質的解法謝謝大家 Problem For an array A, if i < j, and A[i] > A[j], called (A[i], A[j]) is a reverse pair.return total of reverse pairs in A. Example Given A = [2, 4, 1, 3, ...

tigerZH 2019-08-14 15:33 評論0 收藏0
[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 評論0 收藏0
[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 評論0 收藏0