diff options
-rw-r--r-- | partition_arr_pivot.c | 43 | ||||
-rw-r--r-- | partition_arr_pivot.py | 39 |
2 files changed, 82 insertions, 0 deletions
diff --git a/partition_arr_pivot.c b/partition_arr_pivot.c new file mode 100644 index 0000000..39e7825 --- /dev/null +++ b/partition_arr_pivot.c @@ -0,0 +1,43 @@ +// 2161. Partition Array According to Given Pivot +#include "leetcode.h" + +/* + * you are given a 0-indexed integer array 'nums' and an integer 'pivot'. + * rearrange 'nums' such that the following conditions are satisfied: every + * element less than 'pivot' appears befor every element greater than 'pivot', + * every element equal to 'pivot' appears in between the elements less than and + * greater than 'pivot', the relative order of the elments less than 'pivot' and + * the elements greater than 'pivot' is maintained. return 'nums' after the + * rearrangement + */ + +int *pivotArray(int *nums, int numsSize, int pivot, int *returnSize) { + int *ans = (int *)malloc(numsSize * sizeof(int)); + int idx = 0; + for (int i = 0; i < numsSize; i++) + if (nums[i] < pivot) + ans[idx++] = nums[i]; + for (int i = 0; i < numsSize; i++) + if (nums[i] == pivot) + ans[idx++] = nums[i]; + for (int i = 0; i < numsSize; i++) + if (nums[i] > pivot) + ans[idx++] = nums[i]; + *returnSize = numsSize; + return ans; +} + +int main() { + int n1[] = {9, 12, 5, 10, 14, 3, 10}, rs1; + int n2[] = {-3, 4, 3, 2}, rs2; + int *pa1 = pivotArray(n1, ARRAY_SIZE(n1), 10, &rs1); + int *pa2 = pivotArray(n2, ARRAY_SIZE(n2), 2, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", pa1[i]); // expect: 9,5,3,10,10,12,14 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", pa2[i]); // expect: -3,2,4,3 + printf("\n"); + free(pa1); + free(pa2); +} diff --git a/partition_arr_pivot.py b/partition_arr_pivot.py new file mode 100644 index 0000000..7c8a305 --- /dev/null +++ b/partition_arr_pivot.py @@ -0,0 +1,39 @@ +# 2161. Partition Array According to Given Pivot + +""" +you are given a 0-indexed integer array 'nums' and an integer 'pivot'. +rearrange 'nums' such that the following conditions are satisfied: every +element less than 'pivot' appears befor every element greater than 'pivot', +every element equal to 'pivot' appears in between the elements less than and +greater than 'pivot', the relative order of the elments less than 'pivot' and +the elements greater than 'pivot' is maintained. return 'nums' after the +rearrangement +""" + + +class Solution(object): + def pivotArray(self, nums, pivot): + """ + :type nums: List[int] + :type pivot: int + :rtype: List[int] + """ + ans = [0] * len(nums) + left, right = 0, len(nums) - 1 + for i, j in zip(range(len(nums)), range(len(nums) - 1, -1, -1)): + if nums[i] < pivot: + ans[left] = nums[i] + left += 1 + if nums[j] > pivot: + ans[right] = nums[j] + right -= 1 + while left <= right: + ans[left] = pivot + left += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.pivotArray(nums=[9, 12, 5, 10, 14, 3, 10], pivot=10)) + print(obj.pivotArray(nums=[-3, 4, 3, 2], pivot=2)) |