Содержание
Я играл с проблемой moving all 0's to end массивов в разных интервью в разных комбинациях. Иногда я прошу переместить все 0 в начало массива, сортируя массив без какой-либо структуры данных и так далее.
В этом уроке мы рассмотрим простой пример перемещения всех нулей, чтобы закончить сохранение порядка массива. Есть два подхода.
Подход-1)
QuickSort Разбиение логики. Что такое точка разворота?
Pivot pointявляется ключевым элементом в алгоритме быстрой сортировки . Он выполняет и разбивает коллекцию вокруг точки поворота.- Он размещает элементы массива, большие, чем пивот, перед ним, а элементы, большие, чем пивот, находятся после него.
- Продолжить через цикл, чтобы отсортировать массив
Логика очень проста:
- Итерация по массиву.
- Если массив [i] не равен 0, то заменить его текущим индексом .
- Если массив [i] == 0, просто пропустите цикл
- В нашем случае
0 is a Pivot point, - Каждый раз, когда мы нашли 0, поворот счетчика будет увеличиваться, и элемент будет перемещаться до точки вращения.
Подход-1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
частный статический недействительным подхода1 ( int [ ] crunchifyData ) {
// Переместить 0 в конец массива
ИНТ J знак равно 0 ;
за ( int я знак равно 0 ; я < crunchifyData . длина ; я ++ ) {
если ( crunchifyData [ i ] ! знак равно 0 ) {
ИНТ температура знак равно crunchifyData [ j ] ;
crunchifyData [ j ] знак равно crunchifyData [ i ] ;
crunchifyData [ i ] знак равно темп ;
j ++ ;
}
}
log ( / n / nApproach-1 Результат: + Массивы . toString ( crunchifyData ) ) ;
}
|
Подход-2)
- Создать новый массив с таким же размером
- Выполните итерацию по массиву и пропустите добавление 0
Подход-2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
частный статический недействительным подхода2 ( int [ ] crunchifyData ) {
int [ ] Num знак равно новый int [ crunchifyData . длина ] ;
ИНТ J знак равно 0 ;
за ( int я знак равно 0 ; я < crunchifyData . длина ; я ++ ) {
если ( crunchifyData [ i ] ! знак равно 0 ) {
Num [ I — j ] знак равно crunchifyData [ i ] ;
} еще {
j ++ ;
}
}
Система. вне. print ( / n / nApproach-2 Результат: + Массивы . toString ( num ) ) ;
}
|
Вот полная программа :
CrunchifyMoveAll0ToEnd.java
CrunchifyMoveAll0ToEnd.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
пакет crunchify. ком . учебник ;
импорт Java . Util. Массивы ;
/ **
*
* @author Crunchify.com
* Требование: переместить все 0 в конец порядка сохранения массива.
* Входной массив: 8 8 3 0 4 0 6 0 9 1
* Выходной массив: 8 8 3 4 6 9 1 0 0 0
*
* /
общественности учебный класс CrunchifyMoveAll0ToEnd {
общественности статический недействительным main ( Строка [ ] аргументы ) {
int [ ] crunchifyData ;
crunchifyData знак равно новый int [ ] { 8 , 8 , 3 , 0 , 4 , 0 , 6 , 0 , 9 , 1 } ;
log ( Исходный массив: + Массивы . toString ( crunchifyData ) ) ;
если ( crunchifyData == ноль | | crunchifyData . длина == 0 ) {
log ( «Пустой массив» ) ;
}
approach1 (crunchifyData);
approach2 (crunchifyData);
}
частный статический недействительным подхода1 ( int [ ] crunchifyData ) {
// Переместить 0 в конец массива
ИНТ J знак равно 0 ;
за ( int я знак равно 0 ; я < crunchifyData . длина ; я ++ ) {
если ( crunchifyData [ i ] ! знак равно 0 ) {
ИНТ температура знак равно crunchifyData [ j ] ;
crunchifyData [ j ] знак равно crunchifyData [ i ] ;
crunchifyData [ i ] знак равно темп ;
j ++ ;
}
}
log ( / n / nApproach-1 Результат: + Массивы . toString ( crunchifyData ) ) ;
}
// Создать новый массив с таким же размером
// Перебираем массив и пропускаем добавление 0
частный статический недействительным подхода2 ( int [ ] crunchifyData ) {
int [ ] Num знак равно новый int [ crunchifyData . длина ] ;
ИНТ J знак равно 0 ;
за ( int я знак равно 0 ; я < crunchifyData . длина ; я ++ ) {
если ( crunchifyData [ i ] ! знак равно 0 ) {
Num [ I — j ] знак равно crunchifyData [ i ] ;
} еще {
j ++ ;
}
}
Система. вне. print ( / n / nApproach-2 Результат: + Массивы . toString ( num ) ) ;
}
частный статический недействительным log ( Строка строка ) {
Система. вне. печать ( строка + ) ;
}
}
|
Выход консоли Eclipse:
|
1
2
3
4
5
|
Исходный массив : [ 8 , 8 , 3 , 0 , 4 , 0 , 6 , 0 , 9 , 1 ]
Подход — 1 Результат : [ 8 , 8 , 3 , 4 , 6 , 9 , 1 , 0 , 0 , 0 ]
Подход — 2 Результат : [ 8 , 8 , 3 , 4 , 6 , 9 , 1 , 0 , 0 , 0 ]
|
Дайте мне знать, если вы знаете лучший способ решить эту проблему. Я хотел бы услышать ваши мысли.
0.00 (0%) 0 votes
