Repository navigation
Expand file tree
/
Copy pathPartition Array.java
More file actions
75 lines (55 loc) · 1.73 KB
/
Copy pathPartition Array.java
File metadata and controls
75 lines (55 loc) · 1.73 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:
All elements < k are moved to the left
All elements >= k are moved to the right
Return the partitioning index, i.e the first index i nums[i] >= k.
Example
If nums=[3,2,2,1] and k=2, a valid answer is 1.
Note
You should do really partition in array nums instead of just counting the numbers of integers smaller than k.
If all elements in nums are smaller than k, then return nums.length
Challenge
Can you partition the array in-place and in O(n)?
Tags Expand
Two Pointers Sort Array
Thoughts:
Two pointer sort, still similar to quick sort.
Move small to left and large to right.
When the two pinter meets, that's crossing point about pivot k
*/
public class Solution {
/**
*@param nums: The integer array you should partition
*@param k: As description
*return: The index after partition
*/
public int partitionArray(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
return helper(nums, 0, nums.length - 1, k);
}
public void swap(int[] nums, int x, int y){
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
public int helper(int[] nums, int start, int end, int pivot) {
int low = start;
int high = end;
while (low <= high) {
while(low <= high && nums[low] < pivot) {
low++;
}
while(low <= high && nums[high] >= pivot) {
high--;
}
if (low <= high) {
swap(nums, low, high);
low++;
high--;
}
}
return low;
}
}