Source: Diffk II

Given an array A of integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.

Example :

Input :

A : [1 5 3]
k : 2

Output :

1

as 3 - 1 = 2

  • Return 0 / 1 for this problem.

解題：

  1. 首先題目並未要求 i 必須大於或小於 j 故 i, j 兩個序列值是可以互換的，也就是說題目要我們做的其實是找到輸入陣列值中是否存在任何一組序列值可以符合以下條件： 
    |A[i] - A[j]| = k, i != j
  2. 當然，這題用兩層 for loop 就可以找到是否存在符合的序列值組合，但藉由使用 hashmap ，可以將複雜度由 O(n^2) 降低至 O(n) 。至於要如何達成呢？因題目已說明目標值 k 不為負數故可以確定以下條件： 
    If A[i] > A[j] and A[i] - A[j] = k, 
then A[i] = A[j] + k, A[j] = A[i] - k, A[i] >= k
If A[j] > A[i] and A[j] - A[i] = k,
then A[i] = A[j] - k, A[j] = A[i] + k, A[j] >= k
  3. 在得到上面的條件後，就可以用 hashmap 來建立對應值： 
    當A[i] >= k 時，hashmap 內的對應值 A[j] 應採用 A[i] - k；
反之當 A[i] < k 時，hashmap 內的對應值 A[j] 應改採 A[i] + k

    而測試是否存在符合條件之組合，只須在迴圈內對字典進行 A[j] 的對應值呼叫即可；換句話說，當沒找到對應值時表示迴圈目前還停在只有遇到其中一個數值 A[i] 的階段，在這階段我們在字典內建立相對應的 A[j] ，並在迴圈推進過程中確認是否存在序列值 j 來達成題目所要求的條件。

Code:

class Solution:
    # @param A : tuple of integers
    # @param k : integer, non negative
    # @return an integer
    def diffPossible(self, A, k):
        """
        i can be greater or smaller than j
        so the condition can be modified as
        |A[i] - A[j]| = k
        """
        checklist, n = dict(), len(A)
        for i in range(n):
            if A[i] > k:
                try:
                    if checklist[A[i]]: return 1
                except:
                    checklist[A[i]-k] = i+1
            else:
                try:
                    if checklist[A[i]]: return 1
                except:
                    checklist[A[i]+k] = i+1
        return 0

GitHub: GitHub

發表留言