파비의 매일매일 공부기록

2023.03.01 Today's Challenge 본문

Problem Solving/LeetCode

2023.03.01 Today's Challenge

fabichoi 2023. 3. 1. 23:45

https://leetcode.com/problems/sort-an-array/

 

Sort an Array - LeetCode

Can you solve this real interview question? Sort an Array - Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smalles

leetcode.com

버블 소트로 풀었는데 당연하게 TL -_-;

Heap Sort로 풀면 풀림.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def heapify(nums, n, i):
            l = 2*i + 1
            r = 2*i + 2

            largest = i

            if l < n and nums[largest] < nums[l]:
                largest = l

            if r < n and nums[largest] < nums[r]:
                largest = r
            
            if largest != i:
                nums[i], nums[largest] = nums[largest], nums[i]
                heapify(nums, n, largest)
            
        n = len(nums)

        for i in range(n//2+1)[::-1]:
            heapify(nums, n, i)
        
        for i in range(n)[::-1]:
            nums[i], nums[0] = nums[0], nums[i]
            heapify(nums, i, 0)
        
        return nums
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.03.03 Today's Challenge  (0) 2023.03.03
2023.03.02 Today's Challenge  (0) 2023.03.02
2023.02.28 Today's Challenge  (0) 2023.02.28
2023.02.27 Today's Challenge  (0) 2023.02.27
2023.02.26 Today's Challenge  (0) 2023.02.26
'Problem Solving/LeetCode' Related Articles more
Comments