Tarkibga o'tish

1920 - Build Array from Permutation

🇬🇧 Inglizcha: Given a zero-based permutation nums (0-indexed), build an array ans of the same length where !# ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

🇺🇿 O'zbekcha: Nolga asoslangan ya'ni index 0 dan boshlanuvchi nums permutatsiya berilgan. Shu bilan bir xil uzunlikda ans array yaratib 0 <= i < nums.length oraliqda ans[i] = nums[nums[i]] tenglab natijani qaytarish kerak ekan.

🟢 Misol 1

$ Input: nums = [0,2,1,5,3,4]
$ Output: [0,1,2,4,5,3]
$ Explanation: The array ans is built as follows: 
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

🟢 Misol 2

$ Input: nums = [5,0,1,2,3,4]
$ Output: [4,5,0,1,2,3]
$ Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

🔴 Cheklovlar

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < nums.length
  • The elements in nums are distinct.

1⃣ - Yechim: LINK

Agar yangi array yaratmay to'g'ridan to'g'ri nums[i] = nums[nums[i]] ga tenglab qo'ysak bizda nums[i] ni o'zida turgan qiymat yo'qolib qoladi shu sababli ans list yaratib olamiz. ans uzunligi(length) nums uzunligi bilan teng bo'lgani sababli yaratish davrida boshlang'ich 0 qiymat berib chiqamiz keyin sikl yaratib ushbu siklda ans[i] = nums[nums[i]] ga tenglab olamiz va ans ni natija sifatida qaytarib yuboramiz.

⏰ Time Complexity: O(n)
📦 Space Complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Author: Abdulaminkhon Khaydarov
# Date: 30/10/22 
# Problem URL: https://leetcode.com/problems/build-array-from-permutation/

from typing import List


class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        # "nums" ni uzunligi bilan teng "ans" listini yaratib olamiz
        ans: List[int] = [0 for _ in nums]

        # "0" dan "nums" uzunligigacha sikl yaratib "ans[i]" ni "nums[nums[i]]" ga tenglab chiqamiz.
        for i in range(len(nums)):
            ans[i] = nums[nums[i]]

        return ans


if __name__ == '__main__':
    solution = Solution()

    # Example 1
    print(solution.buildArray([0, 2, 1, 5, 3, 4]) == [0, 1, 2, 4, 5, 3])

    # Example 2
    print(solution.buildArray([5, 0, 1, 2, 3, 4]) == [4, 5, 0, 1, 2, 3])

2⃣ - Yechim: LINK

Birinchi yechimda biz qo'shimcha array dan foydalandik. Buni qo'shimcha array ishlatmay ishlash usuli mavjud biz bunda xotiradan constant joy ishlatamiz. nums ni uzunligini n ga tenglab olamiz keyin 0 dan n gacha sikl ochamiz bunda har bir sikl bosqichida biz nums[i] ni num ga tenglab turamiz. Agar biz nums[num] ni n ga bo'lib qoldiqni olsak bizda hozirgi nums[i] teng bo'ladigan qiymat kelib chiqadi va buni biz b o'zgaruvchisiga saqlab turamizda nums[i] da turgan qiymatga n * b + num shuni tenglab qo'yamiz. Bizga yana bitta sikl kerak bo'ladi, bu ham 0 dan n gacha bo'ladi. Biz nums[i] ni n ga bo'lib butun qismini olsak bizga avvalroq saqlab qo'ygan qiymatimizni qaytaradi va buni nums[i] ga tenglab qo'yamiz.

⏰ Time Complexity: O(n)
📦 Space Complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Author: Abdulaminkhon Khaydarov
# Date: 30/10/22 
# Problem URL: https://leetcode.com/problems/build-array-from-permutation/

from typing import List


class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        # nums ni uzunligini n ga tenglab olamiz.
        n = len(nums)

        for i in range(len(nums)):
            # "nums[i]" elementini vaqtincha "num" ga olib turamiz
            num = nums[i]

            # "nums[num]" elementini "n" ga bo'lib qoldiqni "b" ga tenglab turamiz.
            b = nums[num] % n

            # "nums[i]" ga "n * b + num" ni tenglab olamiz.
            nums[i] = n * b + num

        for i in range(len(nums)):
            # "nums[i]" ni "nums[i]" ni "n" ga bo'lib butun qismiga tenglab olamiz.
            nums[i] = nums[i] // n

        return nums


if __name__ == '__main__':
    solution = Solution()

    # Example 1
    print(solution.buildArray([0, 2, 1, 5, 3, 4]) == [0, 1, 2, 4, 5, 3])

    # Example 2
    print(solution.buildArray([5, 0, 1, 2, 3, 4]) == [4, 5, 0, 1, 2, 3])
Oxirgi yangilanish: November 13, 2022 09:15:23