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 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).
Note:
- The pairs (i, j) and (j, i) count as the same pair.
- The length of the array won't exceed 10,000.
- All the integers in the given input belong to the range: [-1e7, 1e7].
C Solution:
void sort(int *nums, int numsSize) {
if (numsSize < 2) return;
int key = nums[numsSize - 1];
int i;
for (i = 0; i < numsSize - 1 && nums[i] < key; i++);
if (i == numsSize - 1) {
sort(nums, numsSize - 1);
return;
}
int j;
for (j = i + 1; j < numsSize - 1; j++) {
if (nums[j] < key) {
nums[j] ^= nums[i];
nums[i] ^= nums[j];
nums[j] ^= nums[i];
i++;
}
}
nums[numsSize - 1] = nums[i];
nums[i] = key;
sort(nums, i);
sort(nums + i + 1, numsSize - i - 1);
}
int findPairs(int* nums, int numsSize, int k) {
if (numsSize < 2) return 0;
sort(nums, numsSize);
int i, j, res = 0;
for (i = 0, j = 1; j < numsSize; ) {
if (nums[j] - nums[i] == k) {
res++;
for (j++; j < numsSize && nums[j - 1] == nums[j]; j++);
continue;
}
if (nums[j] - nums[i] < k) {
for (j++; j < numsSize && nums[j - 1] == nums[j]; j++);
continue;
}
for (i++; i < numsSize && nums[i - 1] == nums[i]; i++);
if (i >= j) j = i + 1;
}
return res;
}
Python Solution 1:
class Solution(object):
def findPairs(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if k < 0: return 0
d = collections.Counter(nums)
if not k:
return sum(int(d[val] > 1) for val in d)
return sum(int(val + k in d) for val in d)
Python Solution 2:
class Solution(object):
def findPairs(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if k < 0: return 0
nums = collections.Counter(nums)
res = 0
for num in nums:
if num + k in nums:
if k:
res += 1
else:
res += 1 if nums[num] > 1 else 0
return res
Summary:
- nothing to say.
LeetCode: 532. K-diff Pairs in an Array
近期评论