前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >lintCode 31 题解

lintCode 31 题解

作者头像
王小明_HIT
发布2020-09-14 16:03:29
发布2020-09-14 16:03:29
3590
举报
文章被收录于专栏:程序员奇点

lintCode 31 题解

  1. 数组划分 中文 English

给出一个整数数组 nums 和一个整数 k。划分数组(即移动数组 nums 中的元素),使得:

代码语言:javascript
复制
所有小于k的元素移到左边
所有大于等于k的元素移到右边

返回数组划分的位置,即数组中第一个位置 i,满足 nums[i] 大于等于 k。样例

例1:

输入: [],9

输出: 0

例2:

输入: [3,2,2,1],2 输出:1 解释: 真实的数组为[1,2,2,3].所以返回 1

挑战

使用 O(n) 的时间复杂度在数组上进行划分。注意事项

你应该真正的划分数组 nums,而不仅仅只是计算比 k 小的整数数,如果数组 nums 中的所有元素都比 k 小,则返回 nums.length。

题解

代码语言:javascript
复制
public class lintCode31 {
    
    public int partitionArray(int[] nums, int k) {
        if(nums == null || nums.length ==0) return 0;
        int start = 0;
        int end = nums.length -1;
        while(start < end){
            
            while(nums[end] >= k  && start < end){
                end--;
            }
            
            while(nums[start] < k && start < end){
                start++;
            }
            
            if(start < end){
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
            }
        }
        if(nums[start] > k){
            return start;
        }else{
            return start+1;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{3,2,2,1};
        int k = 2;
        
        System.out.println(new lintCode31().partitionArray(nums, k));

    }

}

欢迎关注公众号:程序员开发者社区
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-09-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员奇点 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • lintCode 31 题解
    • 题解
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档