欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

lintcode-31. Partition Array

程序员文章站 2022-03-24 17:44:20
...

1. 问题描述

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.

Challenge
Can you partition the array in-place and in O(n)?

2. my solution

2.1 我的思路

首先, 我之后在找别的solution的时候才发现大家没有注意到下面几个点

  • 题目中并没有要求返回数组, 也就是数组并不需要更改
  • 题目中没有要求数组一定是有序的, 只需要小的在左边, 大的在右边即可

少了上面两个误区, 可以构造以下思路
建立一个新的数组大小与输入数组一样, 从0开始遍历数组, 如果比k小就放到最左边, 如果比k大就放到最右边

  • 时间复杂度: O(n) (完成挑战)

2.2 代码实现


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 lo = 0 ;
        int hi = nums.length- 1;
        int[] r = new int[nums.length];
        
        
        for(int i = 0 ;i<nums.length; i++)
        {
            if(nums[i] < k)
                r[lo++]  = nums[i];
            else
                r[hi--] = nums[i];
        }
        return lo;
    }
}

2.3 运行结果

可以看到结果还是不错的
lintcode-31. Partition Array