首页 > 代码库 > LintCode-Partition Array
LintCode-Partition Array
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.
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"
Example
If nums=[3,2,2,1] and k=2, a valid answer is 1.
Challenge
Can you partition the array in-place and in O(n)?
Solution:
1 public class Solution { 2 /** 3 *@param nums: The integer array you should partition 4 *@param k: As description 5 *return: The index after partition 6 */ 7 public int partitionArray(ArrayList<Integer> nums, int k) { 8 //if (nums.isEmpty()) return 0; 9 int len = nums.size();10 if (len==0) return 0;11 12 int p1 = 0, p2 = len-1;13 while (p1<len && nums.get(p1)<k) p1++;14 while (p2>=0 && nums.get(p2)>=k) p2--;15 16 while (p1<p2){17 //swap the element at p1 and p2.18 int temp = nums.get(p1);19 nums.set(p1,nums.get(p2));20 nums.set(p2,temp);21 22 //Move p1 and p2.23 p1++;24 while (p1<len && nums.get(p1)<k) p1++;25 p2--;26 while (p2>=0 && nums.get(p2)>=k) p2--;27 }28 29 return p1;30 }31 }
LintCode-Partition Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。