专栏首页desperate633LintCode 交错正负数题目分析代码

LintCode 交错正负数题目分析代码

题目

给出一个含有正整数和负整数的数组,重新排列成一个正负数交错的数组。

注意事项

不需要保持正整数或者负整数原来的顺序。

样例 给出数组[-1, -2, -3, 4, 5, 6],重新排序之后,变成[-1, 5, -2, 4, -3, 6]或者其他任何满足要求的答案

分析

最简单的思路显然是用两个数组记录正数和负数,最后在遍历一遍即可

要求原地完成的思路: 两根指针,首先判断正数多还是负数多,并把多的那一部分移到后半部分,最后两根指针分别递增二交换即可 具体思路看代码注释

代码

class Solution {
    /**
     * @param A: An integer array.
     * @return: void
     */
    public int[] rerange(int[] A) {
        // Check the input parameter.
        if(A == null || A.length < 3)
            return A;
        
        int n = A.length;
        
        int countPositive = 0;//计算正数的个数
        
        
        
        // store the positive numbers index.
        int positiveIndex = 0;
        int pos = 1;
        int neg = 0;
        for(int i=0;i<n;i++) {
                if(A[i] > 0) {
                // Put all the positive numbers at in the left part.
                    swap(A,positiveIndex++,i);
                    countPositive++;
                }
        }
        
        if(countPositive > n/2) {
        // If positive numbers are more than negative numbers,
        // Put the positive numbers at first.
            pos = 0;
            neg = 1;
            // Reverse the array.
            
            int left = 0;
            int right = n-1;
            while(left < right) {
                swap(A,left,right);
                left++;
                right--;
            }
        }
        
        while(pos < n && neg <n) {
            while(pos<n && A[pos]>0)
                pos +=2;
            while(neg<n && A[neg]<0)
                neg +=2;
            if(neg >= n || pos>=n)
                break;
            swap(A,pos,neg);
        }
        
        // Reorder the negative and the positive numbers.
       
            // Should move if it is in the range.
            
            // Should move if it is in the range.
       return A; 
   }
   
   public void swap(int[] A, int l, int r) {
       int temp = A[l];
       A[l] = A[r];
       A[r] = temp;
   }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 最长公共子串代码

    desperate633
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633
  • [编程题] 赶去公司代码

    终于到周末啦!小易走在市区的街道上准备找朋友聚会,突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域,每条街道假设坐标是(X,...

    desperate633
  • Google Code Jam 2020 Qualification Round: Vestigium Solution

    Google Code Jam 2020 Qualification Round: Vestigium Solution

    包子面试培训
  • 翻转瓷砖Fliptile(开关反转)- POJ 3279

    Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

    ACM算法日常
  • BZOJ 3053: The Closest M Points(K-D Tree)

    attack
  • 仿qq最新侧滑菜单

    为了后续对这个项目进行优化,比如透明度动画、背景图的位移动画,以及性能上的优化。 我把这个项目上传到github上面,请大家随时关注。 github地址 htt...

    xiangzhihong
  • 搜索专题3 | 八数码 HDU - 1043

    本搜索专题会参考vjudge上的《kuangbin带你飞》系列题目,前面2篇是基础题,后面会慢慢复杂起来!加油!

    ACM算法日常
  • Java字节码修改库ASM#ClassReader实现原理及源码分析

    ASM是Java中比较流行的用来读写字节码的类库,用来基于字节码层面对代码进行分析和转换。

    JavaEdge
  • HDU 5652 India and China Origins(并查集)

    India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit:...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券