Facebook面试题 Moving positive, negative and zeros in an array

深碍√TFBOYSˉ_ 2022-07-13 12:48 179阅读 0赞

> Given an input int array with positive, negative numbers and 0s. Putting negative number on the left side, zero in the middle and positive on the right side. Do it in `O(n)` time and `O(1)` space.

*  Analysis:  
    This question is very similar to [*Sorting Colors*][Sorting Colors]. We just need to keep 2 pointers for the last position of negative numbers and first place of positive numbers and put numbers to its corresponding position during traversal. Zeros will be in the middle automatically.

Java implementation is showed as following:

public class Solution {
        public void movingNumber(int[] nums) {
            if (nums == null || nums.length == 0) {
                return;
            }
    
            int start = 0;
            int end = nums.length - 1;
    
            for (int i = 0; i <= end; i++) {
                if (nums[i] < 0) {
                    swap(nums, i, start);
                    start++;
                }
                if (nums[i] > 0) {
                    swap(nums, i, end);
                    end--;
                    i--;
                }
            }
        }
    
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

[Sorting Colors]: https://github.com/YaokaiYang-assaultmaster/LeetCode/blob/master/75.%20Sort%20Colors

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关 LIGHTOJ-1294 - Positive Negative Sign

1294 - Positive Negative Sign <table> <tbody> <tr> <td title="normal judge" st

淡淡的烟草味﹌/ 2022年08月18日 02:10/ 0 赞/ 135 阅读

相关 LeetCode-Move Zeroes

Problem: > > Given an array `nums`, write a function to move all `0`'s to the end of

Dear 丶/ 2022年08月09日 03:24/ 0 赞/ 154 阅读

相关 Counting positive and negative number and computing the average of numbers

代码： import java.util.Scanner; public class Ten_six {

雨点打透心脏的1/2处/ 2022年08月09日 02:19/ 0 赞/ 213 阅读

相关 Facebook面试题 Moving positive, negative and zeros in an array

> Given an input int array with positive, negative numbers and 0s. Putting negative numb

深碍√TFBOYSˉ_/ 2022年07月13日 12:48/ 0 赞/ 180 阅读

相关 Facebook面试题 find the peek or valley index in an array

> Given an input array in which `A[i] = A[i - 1] -1/+1`. And there is only one peek or o

缺乏、安全感/ 2022年07月13日 11:47/ 0 赞/ 60 阅读

相关 Facebook面试题 Suffix array sorting

Given a suffix array. E.g. `int[] text = {10, 20, 30, 25}`, then `suffix[0] = {10, 20, 3

清疚/ 2022年07月13日 08:23/ 0 赞/ 105 阅读

相关 Facebook面试题 Find first k common elements in n sorted arrays

> Given n sorted arrays, find first k common elements in them. > E.g. the common eleme

淩亂°似流年/ 2022年07月13日 07:11/ 0 赞/ 129 阅读

相关 283. Move Zeroes

Given an array `nums`, write a function to move all `0`'s to the end of it while maintai

爱被打了一巴掌/ 2022年06月12日 06:15/ 0 赞/ 166 阅读

相关 283.Move Zeroes

/ DescriptionHintsSubmissionsSolutions Given an array nums, write

Bertha 。/ 2022年06月09日 03:55/ 0 赞/ 179 阅读

相关 Find First and Last Position of Element in Sorted Array - LeetCode

目录题目链接注意点解法小结题目链接 [Find First and Last Position of Element in Sort

我会带着你远行/ 2021年09月30日 15:06/ 0 赞/ 194 阅读