Partition Array-布布扣-bubuko.com

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.

技术分享图片

这图片是真滴大。。。

这道题目，换个方式，即是说，比k小的有多少个数，有两种方法：

1）升序排序，然后遍历，遇到第一个 >=k 的数即可返回，代码如下：

public class Solution {
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
        // write your code here
        int length = nums.length;
        if(length == 0){
            return 0;
        }
        sort(nums);
        for(int i = 0; i < length; i++){
            if(nums[i] >= k){
                return i;
            }
        }
        return length;
    }
    
    public static void sort(int[] nums){
        int length = nums.length;
        for(int i = 0; i < length; i++){
            for(int j = i+1; j < length; j++){
                if(nums[i] > nums[j]){
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
        }
    }
}

这道题的要求其实比较低，试着手写了一个冒泡排序代进去，还是可以通过的；

2）遍历数组，统计比k小的数count，那么可能出现的情况有：

　　a)count == 0，即数组中所有元素都>=k，按照题目要求，此时应该返回0；

　　b)count > 0 && count < length，那么说明数组中有count个数比k要小：返回k；

　　c)count == length，即所有元素都比k要小，按照题目要求，此时应该返回length；

综上：

public class Solution {
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
        // write your code here
        int length = nums.length;
        if(length == 0){
            return 0;
        }
       int count = 0;
       for(int i = 0; i < length; i++){
           if(nums[i] < k){
               count++;
           }
       }
       if(count > 0){
           if(count == length){
                return length;
           }else{
               return count;
           }
       }
       return 0;
       
    }
}

不知道是否有其他思路（至少目前的我想不到哈哈哈）

Partition Array

Description