Flashcards
Untitled
Cards in this deck (2)
- 1The Dutch national flag Solution 1 (brute force):
o Create 3 new arrays: smaller, equal, greater
o Loop through each item and move to appropriate array
o Time complexity: O(n), space complexity: O(n)
Solution 2: (dumb)
Solution 3:
o 2 passes
o First pass: loop through and check if element is smaller than pivot then swap with the “wall”
o Second pass: similar but do with greater items
o Time complexity: O(n), space complexity: O(1)
Solution 4: (concise)
o Consider 4 sub arrays: smaller, equal, unclassified, greater
o Loop through all elements, if smaller then swap with smaller’s wall & increase smaller’s wall, if equal then increase equal’s wall, else if larger then swap with larger’s wall (inverse way) & decrease larger’s wall
o Time complexity: O(n), space complexity: O(1) - 2Increment an arbitrary-precision integer Solution 1 (brute force):
o Convert array to actual integer, increment, then convert back
o Cons: what if integer out of range
Solution 2:
o Increase from the last digit, if > 10 then get the least significant digit, and increment the previous digit
o If out of space of array, set first digit as 0, and add(0,1) so that all remaining digits follow
Information
- Description
- Flashcards on Untitled, created by Duc Tran on 22/05/2018.
- Created by
- Duc Tran · May 2018
- Updated
- May 22, 2018
- Views
- 0
- Rating