遍历数组排序,负数在左,正数在右

栏目: Java · 发布时间: 5年前

内容简介:有一个整形数组,包含正数和负数,然后要求把数组内的所有负数移至正数的左边,且保证相对位置不变,要求时间复杂度为O(n), 空间复杂度为O(1)。例如,{10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35}变化后是{-2, -4,-3, -88, -23,5, 8 ,10, 2, 7, 12, 35}。实现原理是:两个变量记录左右节点,两边分别开始遍历。左边的节点遇到负值继续前进,遇到正值停止。右边的节点正好相反。然后将左右节点的只进行交换,然后再开始遍历直至左右节点相遇

问题描述:

有一个整形数组,包含正数和负数,然后要求把数组内的所有负数移至正数的左边,且保证相对位置不变,要求时间复杂度为O(n), 空间复杂度为O(1)。例如,{10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35}变化后是{-2, -4,-3, -88, -23,5, 8 ,10, 2, 7, 12, 35}。

解决方法

实现原理是:两个变量记录左右节点,两边分别开始遍历。左边的节点遇到负值继续前进,遇到正值停止。右边的节点正好相反。然后将左右节点的只进行交换,然后再开始遍历直至左右节点相遇。

这种方式的时间复杂度是O(n).空间复杂度为O(1)

以下为 java 的实现:

public void setParted1(int[] a, int left, int right) {
        if (left >= right || left == a.length || right == 0) {
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
            return;
        }
        while (a[left] < 0) {
            left++;
        }
        while (a[right] >= 0) {
            right--;
        }
        if (left >= right || left == a.length || right == 0) {
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
            return;
        }
        swap(a, left, right);
        left++;
        right--;
        setParted1(a, left, right);
    }

    private void swap(int a[], int left, int right) {
        int temp = 0;
        temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }

热度: 2


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

共享经济大趋势

共享经济大趋势

倪云华 虞仲轶 / 2016-1-1 / 49.00

2015年互联网界乃至整个商界的最热门字眼,恐怕就是“共享经济”了。共享经济模式正以前所未有的速度与规模席卷全球。那么,共享经济为什么会产生?其本质是什么?共享经济会为我们带来什么价值?成功的共享经济商业模式是怎样的?如何管理和运作一家共享经济企业?在未来,共享经济还将面临哪些挑战?共享经济的下一个发展机会在哪里?传统经济又该如何应对? 作为国内第一本系统性阐述共享经济的书籍,本书通过对全球......一起来看看 《共享经济大趋势》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具