LintCode 数组划分题目分析代码

题目

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

所有小于k的元素移到左边 所有大于等于k的元素移到右边 返回数组划分的位置,即数组中第一个位置 i,满足 nums[i] 大于等于 k。

注意事项

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

样例 给出数组 nums = [3,2,2,1] 和 k = 2,返回 1.

分析

很简单,快速排序的partiton,两根指针一头一尾

代码

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 == null || nums.length == 0){
            return 0;
        }
        
        int left = 0, right = nums.length - 1;
        while (left <= right) {

            while (left <= right && nums[left] < k) {
                left++;
            }

            while (left <= right && nums[right] >= k) {
                right--;
            }

            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                
                left++;
                right--;
            }
        }
        return left;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏抠抠空间

python内置函数大全

 数学运算 abs:求数值的绝对值 >>> abs(-2) 2 divmod:返回两个数值的商和余数 >>> divmod(5,2) (2, 1) >> d...

2926
来自专栏me的随笔

Python中的类、对象、继承

上述访问级别更多的是一种编程约定,即便是以双下划线开头的字段,在类的外部也是可以访问的,但不建议这么做。示例代码如下:

1695
来自专栏步履前行

Java基础系列---操作符

  还记得我们刚开始学习Java的时候记住优先级和逻辑运算符就可以开始工作了,昨天在看到源码的时候发现一个操作符 |=,没有印象,然后去搜了下,发现提到的文章也...

1624
来自专栏尾尾部落

[剑指offer] 包含min函数的栈

用一个栈stack保存数据,用另外一个栈temp保存依次入栈最小的数 比如,stack中依次入栈 5, 3, 4, 10, 2, 12, 1, 8 则te...

1153
来自专栏Python小屋

Python获取numpy数组中最大的5个元素(保持原顺序)

本文主要演示numpy的argsort()函数的用法。这个函数的返回值是数组中的元素排序后的原下标,例如np.argsort([3,1,2])的返回结果是arr...

3646
来自专栏WindCoder

Java漫谈-数组

在Java语言中,数组是对象(An object is a class instance or an array.),而且是动态创建的。

1771
来自专栏塔奇克马敲代码

第 14 章 重载运算与类型转换

2486
来自专栏java一日一条

如何用 JavaScript 实现一个数组惰性求值库

看到函数式语言里面的惰性求值,想自己用 JavaScript 写一个最简实现,加深对惰性求值了解。用了两种方法,都不到 80 行实现了基本的数组的惰性求值。

912
来自专栏流媒体

C++多态

当类存在虚函数时,编译器会为该类维护一个表,这个表就是虚函数表(vtbl),里面存放了该类虚函数的函数指针。在构造类的时候增加一个虚表指针(vptr)指向对应的...

1163
来自专栏GopherCoder

Python 强化训练:第三篇

1204

扫码关注云+社区

领取腾讯云代金券