Find k most frequent in linear time

Given an integer array nums and an integer k (1 ≤ k ≤ number of distinct values in nums), return any k values that appear most frequently. Implement an average-case O(n) time, O(n) space solution using a frequency map and bucket-based grouping; explain why it is linear. Then compare it with a heap-based O(n log k) approach: discuss when each is preferable, memory trade-offs, and how you would break ties. Clarify handling of negative numbers and very large value ranges. Provide code and analyze time and space complexity.