题目
数组划分
给出一个整数数组nums和一个整数k。划分数组（即移动数组nums中的元素），使得：
- 所有小于k的元素移到左边
- 所有大于等于k的元素移到右边
返回数组划分的位置，即数组中第一个位置i，满足nums[i]大于等于k。
您在真实的面试中是否遇到过这个题？
Yes
样例
给出数组nums=[3,2,2,1]和 k=2，返回 1
注意
你应该真正的划分数组nums，而不仅仅只是计算比k小的整数数，如果数组nums中的所有元素都比k小，则返回nums.length。
挑战
要求在原地使用O(n)的时间复杂度来划分数组
解题
快速排序，搞了好久，中间的那个值一直找不到，然后就遍历数组找了。
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) {
//write your code here
if(nums.length==0)
return 0;
int p = partition(nums,0,nums.length-1,k);
if(p==nums.length - 1)
return nums.length;
return p;
}
public int partition(int[] nums,int left,int right,int k){
int i = left;
int j = right;
while(i<j){
while(i<j&&nums[j] >=k) j--;
while(i<j&& nums[i]<k) i++;
if(nums[i]>=k && nums[j]<k){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
j--;
i++;
}
}
for(i=0;i<right;i++)
if(nums[i]>=k)
return i;
return right;
}
}
Java Code
在九章算法中，i<j 换成i<=j 最后输出的i就是所求的答案
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) {
//write your code here
if(nums.length==0)
return 0;
int p = partition(nums,0,nums.length-1,k);
return p;
}
public int partition(int[] nums,int left,int right,int k){
int i = left;
int j = right;
while(i<=j){
while(i<=j&&nums[j] >=k) j--;
while(i<=j&& nums[i]<k) i++;
if(i<j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
j--;
i++;
}
}
return i;
}
}
Java Code
class Solution:
"""
@param nums: The integer array you should partition
@param k: As description
@return: The index after partition
"""
def partitionArray(self, nums, k):
# write your code here
# you should partition the nums by k
# and return the partition index as description
l = len(nums)
if l == 0:
return 0
i = 0
j = l-1
while i<j:
while i<=j and nums[j]>=k:
j-=1
while i<=j and nums[i]<k:
i+=1
if i<j:
tmp = nums[i]
nums[i]=nums[j]
nums[j]=tmp
i+=1
j-=1
return i
Python Code