请教一道算法题,如下,谢谢!

有一个数组[1,1,1,2,3,4,5,8,10,22,24,25,26,66]
请写一个方法把数组变成[1,1,[1,2,3,4,5],8,10,22,[24,25,26],66]
就是把里面连续递增的数字归成一个数组,没思路,有没有好的方案?

阅读 10k
16 个回答

两个指针 i,j

var arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]
var len = arr.length
var i = 1, j = 0
var rst = []
for(; i <= len; i++) {
  if(arr[i]-arr[i-1] !== 1) {
    i-j===1 ? rst.push(arr[j]) : rst.push(arr.slice(j, i))
    j = i
  }
}

贴个js版的

(function(){
let arr = [1,2,3,1,1,2,3,4,5,8,10,22,24,25,26,66,67];
let result = arr.reduce((res, a, i)=>{
    if(i===0){
        res.push(a);
        return res;
    }
    if(a-arr[i-1] === 1){
        if(!Array.isArray(res[res.length-1])){
            res = [...res.slice(0,-1), [...res.slice(-1)]];
        }
        res[res.length-1].push(a);
    }else{
        res.push(a);
    }
    return res;
}, []);
console.log(result);
})();

一行python版本:

from itertools import groupby

arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]

print([j[0] if len(j) == 1 else j for j in [[i[1] for i in g] for k, g in groupby(enumerate(arr), lambda x: x[1] - x[0])]])

效率和可读性就忽略好了。

再补个朴素易懂的吧:

arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]

res = []
tmp = [arr[0]] if arr else []
arr = arr + [float('inf')]
for i in range(1, len(arr)):
    current, pre = arr[i], arr[i-1]
    if current - pre == 1:
        tmp.append(current)
    else:
        res.extend([tmp] if len(tmp) > 1 else tmp)
        tmp = [current]
print(res)

既然在Go版块看到,那就来个Go版本的吧:

func resort(arr []int) interface{} {
    if len(arr) == 1 {
        return arr
    }
    i, j := 1, 0
    subArr := []interface{}{}
    for ; i < len(arr); i++ {
        if arr[i] != arr[i - 1] + 1 {
            if j == i - 1 {
                subArr = append(subArr, arr[i - 1])
            } else {
                subArr = append(subArr, arr[j:i])
            }
            j = i
        }
    }
    return subArr
}

两个指针不就可以了吗。
注意点就是合并以后后面的指针要减去长度。


function mergeSeq(array) {
    let result = [];
    let arr = [];

    for (let i = 0; i < array.length; i++) {
        let element = array[i];
        arr[0] = element;
        console.log(i);
        for (let j = i + 1; j < array.length; j++) {
            const e = array[j];
            if ((e - element) == 1) {
                arr.push(e);
                element = e;
            } else {
                break;
            }
            i++;
            console.log(i);
        }
        if (arr.length == 1) {
            result.push(arr[0]);
        } else {
            result.push(arr);
        }
        arr = [];
    }
    return result;
}
let array = [
    1,
    1,
    1,
    2,
    3,
    4,
    5,
    8,
    10,
    22,
    24,
    25,
    26,
    66
];
console.log(array.length);
let result = mergeSeq(array);
console.log(result);

快速写了下,没有测试边界

折腾了一下,php版本

$arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66];
$len = count($arr);
sort($arr, SORT_ASC);
$res   = [];
$index = 0;
for ($i = 0; $i < $len - 1; $i++) {
    if ($arr[$i+1] == $arr[$i] + 1) {
        $res[$index][] =  $arr[$i];
        if ($arr[$i+1] + 1 != $arr[$i+2]) {
            $res[$index][] =  $arr[$i+1];
            $i++;
            $index++;
            $res[$index] = $arr[$i+1];
        }
    } else {
        $res[$index] = $arr[$i];
        $index++;
    }
}
echo json_encode($res);
/**
*寻找顺着的数字的规律,或者比前一个数多一,或者比后一个数少一,
*然后分类
*s[i]-1 === s[i-1] || s[i]+1 === s[i+1]
 */
const seq = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]
let rst = []
seq.forEach(function (v, i) {
    if(v+1 === seq[i+1] || v-1 === seq[i-1])
        rst[rst.length -1] instanceof Array ?
        rst[rst.length -1].push(v) :
        rst.push(Array.of(v))
    else
        rst.push(v)
})
console.log(rst)
console.log(seq)

php版,菜鸟的想法:

`<?php 
 $arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66];
 $new_arr = '';
 foreach($arr as $k => $v){
    if($k == 0){
        $new_arr .= $v;
    }else{
        if($arr[$k-1]+1 == $v){
            $new_arr .= ",".$v;
        }else{
            $new_arr .= "#".$v;
        }
    }
 }
 $new_arr_1 = explode("#",$new_arr);
 foreach($new_arr_1 as $k1 => $v1){
    if(strpos($v1,",") !== false){
        $new_arr_2 = explode(",",$v1);
        $new_arr_1[$k1] = $new_arr_2;
    }
 }
 print_r($new_arr_1);
?>`
新手上路,请多包涵
var newArr = arr.reduce((array, item, index) => {
    if(arr[index+1] - item === 1 || item - arr[index-1] === 1) {
        Array.isArray(array[array.length-1]) ? array[array.length-1].push(item) : array.push([item])
    }else {
        array.push(item)
    }
    return array
}, [])

PYTHON

lala = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]
res = []
tmp = [lala[0]]
for i in range(1, lala.__len__()):
    if lala[i] - lala[i-1] == 1:
        tmp.append(lala[i])
    else:
        if len(tmp) == 1:
            res.append(tmp[0])
            tmp = [lala[i]]
        else:
            res.append(tmp)
            tmp = [lala[i]]

print(res)

来个C++的吧,C++不能把int和array同时放到一个array里,所以要用2D arrray

vector<vector<int>> groupNum(vector<int>& nums) { 
    sort(nums.begin(), nums.end()); // in case nums is not in order
    vector<vector<int>> res;
    for(int i : nums) {
        if (res.empty() || res.back().back() != i - 1)
            res.push_back(vector<int>({i}));
        else
            res.back().push_back(i);
    }   
    return res;
}

php版本:

<?php

$arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66];

function sorted_arr($arr) {
    $new_arr = [];
    $sorted_arr= [];
    foreach ($arr as $index => $number) {
        if ((isset($arr[$index + 1]) && $number + 1 == $arr[$index + 1]) || (isset($arr[$index - 1]) && $arr[$index - 1] + 1 == $number)) {
            array_push($sorted_arr, $number);
        } else if (!empty($sorted_arr)){
            array_push($new_arr, $sorted_arr);
            $sorted_arr = [];
        } else {
            array_push($new_arr, $number);
        }    
    }
    return $new_arr; 
}


?>

python

a = [1, 1, 1, 2, 3, 4, 5, 8, 10, 22, 24, 25, 26, 66]
b = []
i = 1
while (i < len(a)):
    if a[i] - a[i - 1] == 1:
        b.append([a[i - 1]])
        for j in range(i, len(a)):
            if a[j] - a[j - 1] == 1:
                b[-1].append(a[j])
            else:
                i = j
                break
    else:
        b.append(a[i])
        i += 1

print(a)
print(b)

我看有个python的答案预先把a[0]放进去了,这是不合法的,因为你不知道如何判断第一个是哪个

太厉害了!有个兄弟发现我的问题了,改进之后的代码如下:

a = [1, 1, 1, 2, 3, 4, 5, 8, 10, 22, 24, 25, 26, 66, 67, 67]
b = []
i = 1
while (i < len(a)):
    if a[i] - a[i - 1] == 1:
        b.append([])
        for j in range(i, len(a)):
            i += 1
            if a[j] - a[j - 1] == 1:
                b[-1].append(a[j - 1])
                print(i)
                if j == len(a) - 1:
                    b[-1].append(a[j])
                    break
            else:
                b[-1].append(a[j - 1])
                if j == len(a) - 1:
                    b.append(a[j])
                break
    else:
        b.append(a[i - 1])
        i += 1

print(a)
print(b)

由于我没有洁癖就不优化代码了,毕竟添加的一个判断不会影响时间复杂度。

$arr = [1,1,2,3,4,5,8,10,22,24,25,26,66];
        $number = count($arr);
        $last_arr = [];
        $temp_arr = [];
        for ($i=1;$i<=$number;$i++){
            if($arr[$i]-$arr[$i-1]==1){
                $temp_arr[]=$arr[$i-1];
            }else{
                if($temp_arr){
                    $temp_arr[] = $arr[$i-1];
                    $last_arr[] = $temp_arr;
                    $temp_arr = [];
                }else{
                    $last_arr[] = $arr[$i-1];
                }
            }
        }
        dump($last_arr);

看到了就一写一个问答,感觉有个前提输入的序列应该是一个非递减序列,然后就是比较前后两个数字的差值,以及临时数组的长度,依次添加到结果数组中即可

def func(a):
    """
    a 输入的数组
    """
    temp = [a[0]] #存放临时数组
    res = [] # 为了不修改原来的数组a 建一个新的list
    i = 1 # i指向前下一个一个数字
    while i < len(a):
        j = i - 1 # 指向前一个数字
        if a[i] - a[j] == 1:
            temp.append(a[i]) # 与前一个数字连续
        else: # 如果不连续
            if len(temp) == 1: #只有一个元素
                res.extend(temp)
            else: # 多个元素的时候
                res.append(temp)
            temp = [a[i]] # 重新开始
        i += 1
    if len(temp):
        if len(temp) == 1: #只有一个元素
            res.extend(temp)
        else: # 多个元素的时候
            res.append(temp)
    return res

if __name__ == "__main__":
    a = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]
    res = func(a)
    print(res)
import itertools

def find_cont(arr):
     arrlen = len(arr)
     def cont_end(begin):
         count = itertools.count(arr[begin])
         for i in range(begin, arrlen):
             if next(count) != arr[i]:
                 return i
         return arrlen

     begin = 0
     while begin < arrlen:
         end = cont_end(begin)
         yield arr[begin:end] if end - begin > 1 else arr[begin]
         begin = end


arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]         
print(list(find_cont(arr)))
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题
宣传栏