#วันที่52ของ #100days_of_coding

วันนี้เป็นวันที่ 52 ของการเขียนโค้ดของฉัน วันนี้ฉันตอบคำถามหนึ่งข้อ

ปัญหา: เมื่อพิจารณาอาร์เรย์ขนาด n และตัวเลข k ให้ค้นหาองค์ประกอบทั้งหมดที่ปรากฏมากกว่า “ n/k “ ครั้ง

เมื่อกำหนดอาร์เรย์จำนวนเต็มขนาด n ให้ค้นหาองค์ประกอบทั้งหมดที่ปรากฏมากกว่า ⌊ n/3 ⌋ ครั้ง

ตัวอย่างที่ 1:

Input: nums = [3,2,3]
Output: [3]

ตัวอย่างที่ 2:

Input: nums = [1]
Output: [1]

ตัวอย่างที่ 3:

Input: nums = [1,2]
Output: [1,2]

ข้อจำกัด:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

ติดตามผล: คุณช่วยแก้ปัญหาในเวลาเชิงเส้นและในปริภูมิ O(1) ได้ไหม

โซลูชัน (ใน java):

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> a= new ArrayList<>();
        HashMap<Integer, Integer> res= new HashMap<Integer, Integer>();
       
        for(int i=0; i<nums.length; i++){
            res.put(nums[i], res.getOrDefault(nums[i], 0) + 1 );
        }
        for( int x: res.keySet()){
            if(res.get(x)> (nums.length / 3 ))
            a.add(x);

        }
        return a;
    }
}