-1
nums = [-1, 2, 3, 5, 7, 9, 9, 9, 11, 1]
nums[:] = set(nums)

#the output for nums is now {1, 2, 3, 5, 7, 9, 9, 9, 11, -1}

I am not sure why calling set moves -1 to the end instead of keeping the code in order. In order to get my desired output I am calling the below code


nums[:] = sorted(set(nums))

For the time complexity of this, calling set() on something would be O(n) and also calling sorted() on something would be O(n) so in total the output would be O(n^2)

Ramen Free Finance
  • 7
  • 1
  • 1
    `set`s and `dict`s [in python](https://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented) are backed by a [Hash Table](https://en.m.wikipedia.org/wiki/Hash_table) data structure. Unlike arrays where an "ordering" of the elements is implied by their [physical locations in RAM](https://en.m.wikipedia.org/wiki/Array_(data_structure)), items in a Hash Tables have no such physical structure. – Him Mar 14 '23 at 22:59
  • 1
    Your time complexity analysis is not correct. You might want to remove those bits from your question and ask for the complexity instead. – Him Mar 14 '23 at 23:01
  • 1
    `sorted` is not O(N), and an O(N) operation followed by another O(N) operation is still O(N). – juanpa.arrivillaga Mar 14 '23 at 23:13
  • "I am not sure why calling set moves -1 to the end " set objects have no particular order. They only guarantee a *consistent* order every time you iterate over it as long as the set hasn't changed. The *reason* this is happening is an implementation detail, and comes down to the size of the set and the hash of integers – juanpa.arrivillaga Mar 14 '23 at 23:14
  • 1
    *"the output for nums is now {1, 2, 3, 5, 7, 9, 9, 9, 11, -1}"* - Not it's not. Only one 9 is left. – Kelly Bundy Mar 14 '23 at 23:24
  • The time complexity depends on the density of your numbers, which you didn't tell us. – Kelly Bundy Mar 14 '23 at 23:25

3 Answers3

1

A set is a data type that can store unique values, without any particular order. So there is no order in a set data type.

Also, the average time complexity of sorted function is O(nlogn). So the total time complexity of the given code is O(nlogn).

In addition, sorted function returns a list and not a set, so this is the reason why you get back the wanted order.

Mark
  • 156
  • 4
-1

There is no "start" or "end" of a set in Python. Sets are fundamentally unordered. The displayed order is completely arbitrary and will depend on a variety of factors that are beyond users' control. This is an intentional design decision and it will not change any time soon.

See https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset for details.

shadowtalker
  • 12,529
  • 3
  • 53
  • 96
-1

Sets are unordered; you cannot expect them to have any particular order.

To work around this, you can use a dict, as its keys preserve insertion order (since Python 3.7).

nums[:] = dict.fromkeys(nums)
Unmitigated
  • 76,500
  • 11
  • 62
  • 80