Сложность: одиночный траверс
blockquote>O(n)
Пожалуйста, позвольте мне добавить мой единственный цикл ответа со сложностью
O(n)
. Я заметил, что во время левого и правого левого перемещения матрицы происходит увеличение и уменьшение на единицу соответственно в индексе строки. Точно так же для верхнего и нижнего верха ход увеличивается и уменьшается наn_cols
. Таким образом, я сделал для этого алгоритм. Например, с учетом матрицы (3x5) с записями, основными индексами строк являются:1,2,3,4,5,10,15,14,13,12,11,6,7,8,9
.------->(+1) ^ 1 2 3 4 5 | (+n_cols) | 6 7 8 9 10 | (-n_cols) | 11 12 13 14 15 (-1)<-------
Решение для кода:
#include <iostream> using namespace std; int main() { // your code goes here bool leftToRight=true, topToBottom=false, rightToLeft=false, bottomToTop=false; int idx=0; int n_rows = 3; int n_cols = 5; int cnt_h = n_cols, cnt_v = n_rows, cnt=0; int iter=1; for (int i=0; i <= n_rows*n_cols + (n_rows - 1)*(n_cols - 1)/2; i++){ iter++; if(leftToRight){ if(cnt >= cnt_h){ cnt_h--; cnt=0; leftToRight = false; topToBottom = true; //cout << "Iter: "<< iter << " break_leftToRight"<<endl; }else{ cnt++; idx++; //cout << "Iter: "<< iter <<" idx: " << idx << " cnt: "<< cnt << " cnt_h: "<< cnt_h<< endl; cout<< idx << endl; } }else if(topToBottom){ if(cnt >= cnt_v-1){ cnt_v--; cnt=0; leftToRight = false; topToBottom = false; rightToLeft=true; //cout << "Iter: "<< iter << " break_topToBottom"<<endl; }else{ cnt++; idx+=n_cols; //cout << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_v: "<< cnt_h<< endl; cout << idx <<endl; } }else if(rightToLeft){ if(cnt >= cnt_h){ cnt_h--; cnt=0; leftToRight = false; topToBottom = false; rightToLeft=false; bottomToTop=true; //cout << "Iter: "<< iter << " break_rightToLeft"<<endl; //cout<< idx << endl; }else{ cnt++; idx--; //cout << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_h: "<< cnt_h<< endl; cout << idx <<endl; } }else if(bottomToTop){ if(cnt >= cnt_v-1){ cnt_v--; cnt=0; leftToRight = true; topToBottom = false; rightToLeft=false; bottomToTop=false; //cout << "Iter: "<< iter << " break_bottomToTop"<<endl; }else{ cnt++; idx-=n_cols; //cout << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_v: "<< cnt_h<< endl; cout<< idx << endl; } } //cout << i << endl; } return 0; }