有一個(gè)數(shù)組[1,1,1,2,3,4,5,8,10,22,24,25,26,66]
,
請(qǐng)寫一個(gè)方法把數(shù)組變成[1,1,[1,2,3,4,5],8,10,22,[24,25,26],66]
就是把里面連續(xù)遞增的數(shù)字歸成一個(gè)數(shù)組,沒(méi)思路,有沒(méi)有好的方案?
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;
}
?>
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);
?>`
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)
我看有個(gè)python的答案預(yù)先把a(bǔ)[0]放進(jìn)去了,這是不合法的,因?yàn)槟悴恢廊绾闻袛嗟谝粋€(gè)是哪個(gè)
太厲害了!有個(gè)兄弟發(fā)現(xiàn)我的問(wèn)題了,改進(jìn)之后的代碼如下:
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)
由于我沒(méi)有潔癖就不優(yōu)化代碼了,畢竟添加的一個(gè)判斷不會(huì)影響時(shí)間復(fù)雜度。
一行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])]])
效率和可讀性就忽略好了。
那就補(bǔ)個(gè)樸素易懂的吧:
arr = [1,1,1,2,3,4,5,8,10,22,24,25,26,66]
tmp = [arr[0]]
res = []
length = len(arr)
for i in range(1, length):
if arr[i] - arr[i-1] == 1:
tmp.append(arr[i])
else:
res.append(tmp[0] if len(tmp) == 1 else tmp)
tmp = [arr[i]]
res.append(tmp[0] if len(tmp) == 1 else tmp)
兩個(gè)指針不就可以了嗎。
注意點(diǎn)就是合并以后后面的指針要減去長(zhǎng)度。
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);
快速寫了下,沒(méi)有測(cè)試邊界
折騰了一下,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);
既然在Go版塊看到,那就來(lái)個(gè)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
}
來(lái)個(gè)C++的吧,C++不能把int和array同時(shí)放到一個(gè)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;
}
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國(guó)IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國(guó)家
北大青鳥中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團(tuán)創(chuàng)建于1999年,經(jīng)過(guò)二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機(jī)構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團(tuán),成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達(dá)內(nèi)教育集團(tuán)成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機(jī)構(gòu),是中國(guó)一站式人才培養(yǎng)平臺(tái)、一站式人才輸送平臺(tái)。2014年4月3日在美國(guó)成功上市,融資1
曾工作于聯(lián)想擔(dān)任系統(tǒng)開(kāi)發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項(xiàng)目經(jīng)理從事移動(dòng)互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍(lán)懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負(fù)責(zé)iOS教學(xué)及管理工作。
浪潮集團(tuán)項(xiàng)目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺(tái)面向?qū)ο箝_(kāi)發(fā)經(jīng)驗(yàn),技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點(diǎn)難點(diǎn)突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫(kù),具有快速界面開(kāi)發(fā)的能力,對(duì)瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁(yè)制作和網(wǎng)頁(yè)游戲開(kāi)發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開(kāi)發(fā)經(jīng)驗(yàn)。曾經(jīng)歷任德國(guó)Software AG 技術(shù)顧問(wèn),美國(guó)Dachieve 系統(tǒng)架構(gòu)師,美國(guó)AngelEngineers Inc. 系統(tǒng)架構(gòu)師。