문제 링크

내 코드

그냥 Brute Force로 다 확인.

1ms, 13.37MB

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        // 길이 500, Brute force로도 충분
        int n = static_cast<int>(arr.size());
        bool answer{};
        for(int i{};i<n;++i) {
            for(int j{i + 1}; j < n; ++j) {
                if(arr[j] == (arr[i] << 1) || arr[i] == (arr[j] << 1)) {
                    answer = true;
                }
            }
        }
        return answer;
    }
};

Solution

Approach 1: Brute Force

• 0ms, 13.43MB
• Complexity
  • Let n be the size of the input array arr.
  • Time Complexity: $O(n^2)$
  • Space Complexity: $O(1)$

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        // Step 1: Iterate through all pairs of indices
        for (int i = 0; i < arr.size(); i++) {
            for (int j = 0; j < arr.size(); j++) {
                // Step 2: Check the conditions
                if (i != j && arr[i] == 2 * arr[j]) {
                    return true;
                }
            }
        }
        // No valid pair found
        return false;
    }
};

Approach 2: Set Lookup

• 2ms, 13.82MB
• Complexity
  • Let n be the size of the input array arr.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> seen;
        for (int num : arr) {
            // Check if 2 * num or num / 2 exists in the set
            if (seen.count(2 * num) || (num % 2 == 0 && seen.count(num / 2))) {
                return true;
            }
            // Add the current number to the set
            seen.insert(num);
        }
        // No valid pair found
        return false;
    }
};

Approach 3: Sorting + Binary Search

• 0ms, 13.38MB
• Complexity
  • Let n be the size of the input array arr.
  • Time Complexity: $O(n \log n)$
  • Space Complexity: $O(\log n)$
    • In C++, the sort() function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worst-case space complexity of $O(\log n)$.

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        // Step 1: Sort the array
        sort(arr.begin(), arr.end());

        for (int i = 0; i < arr.size(); i++) {
            // Step 2: Calculate the target (double of current number)
            int target = 2 * arr[i];
            // Step 3: Custom binary search for the target
            int index = customBinarySearch(arr, target);
            // If the target exists and is not the same index
            if (index >= 0 && index != i) {
                return true;
            }
        }
        // No valid pair found
        return false;
    }

private:
    int customBinarySearch(vector<int>& arr, int target) {
        int left = 0;
        int right = arr.size() - 1;

        while (left <= right) {
            // Avoid potential overflow
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // Target not found
        return -1;
    }
};

Approach 4: Frequency Hash Map

• 4ms, 14.74MB
• Complexity
  • Let n be the size of the input array arr.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_map<int, int> map;

        // Count occurrences of each number
        for (int num : arr) {
            map[num]++;
        }

        for (int num : arr) {
            // Check for double
            if (num != 0 && map.find(2 * num) != map.end()) {
                return true;
            }
            // Handle zero case (ensure there are at least two zeros)
            if (num == 0 && map[num] > 1) {
                return true;
            }
        }
        return false;
    }
};