leetcode数组排序

87 阅读 0 评论 58 点赞

我是靠谱客的博主矮小雪碧，最近开发中收集的这篇文章主要介绍leetcode数组排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

对数组A按照偶数和奇数重新排序，使得偶数在前，奇数在后。可以返回任何一种满足这个条件的数组即可。

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

//判断整数n是否是偶数

func isEven(n int) bool {
if n %2 == 0 {
return true
}
return false
}

解法1、使用选择排序，从第1个元素开始每次从该元素后面找到一个偶数与第一个元素交换，时间复杂度O(N^2)

func sortArrayByParity(A []int) []int {
length := len(A)

for i:=0;i<length-1; i++{
tmp := i
for j:=i+1;j<length; j++{
if isEven(A[j]) {
tmp = j
break
}
}
if tmp !=i {
A[i],A[tmp] = A[tmp],A[i]
}
}
return A
}

解法2 分别从数组的头部和尾部往中间遍历数组，将头部找到的奇数与尾部找到的偶数交换，时间复杂度O(n)

func sortArrayByParity(A []int) []int {
length := len(A)
var istop, jstop = false,false
var i,j = 0, length -1
for i<j {
if !isEven(A[i]) {
istop = true
} else {
i++
istop = false
}
if isEven(A[j]) {
jstop = true
} else {
j--
jstop = false
}

if istop &&jstop {
A[i],A[j] = A[j], A[i]
i++
j--
}
}
return A
}

解法3 从数组的头部往后遍历数组一次，使用两个指针分别指向未排序的第一个元素和下一个需要交换的偶数，时间复杂度O(n)

func sortArrayByParity(A []int) []int {
length := len(A)
var i,j = 0,0
for ;j<length; j++ {
if isEven(A[j]) {
A[i],A[j] = A[j],A[i]
i++
}
}
return A

}