Masalah Java diselesaikan menggunakan algoritma (masalah tentang peta hash)
阿神
阿神 2017-05-27 17:41:09
0
3
626

Soalan pertama leetcode, kaedah ini boleh mencapai penyelesaian kerumitan O(n)

Soalan memerlukan int[], seperti nombor = [2, 7, 11, 15] dan sasaran = 9.
Jika terdapat dua nombor yang jumlahnya ialah nilai sasaran, contohnya nums[0] + nums[1] = 2 + 7 = 9
kembali [0, 1].

Apabila menggunakan penyelesaian berikut, saya mempunyai sedikit keraguan, iaitu, peta cincang baharu dibuat, tetapi tiada nilai diberikan kepadanya Bagaimana anda mencapai keperluan soalan dalam kes ini?

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(target - numbers[i])) {
            result[1] = i + 1;
            result[0] = map.get(target - numbers[i]);
            return result;
        }
        map.put(numbers[i], i + 1);
    }
    return result;
}
阿神
阿神

闭关修行中......

membalas semua(3)
phpcn_u1582

Bukankah map.put() dalam gelung for merupakan tugasan? ? ?

曾经蜡笔没有小新

Soalan memerlukan jumlah dua nombor menjadi nilai sasaran dan nilai yang diberikan, maka anda mesti melintasi sekurang-kurangnya dua nombor
(1) Jika anda memulakan dahulu, ia akan mengambil masa algoritma O(n); cari yang pertama Apabila nilainya betul, masa algoritma ialah O(k), 0<k<n Jumlah masa ialah O(n+k), untuk menentukan sama ada ia adalah diri anda sendiri, seperti (10 = 5 + 5 ).
 Realisasi situasi ini ialah:

.

Nota: Traverse ke nombor pertama yang betul

 
(2) Jika ia tidak dimulakan, ia akan merentasi ke nombor kedua yang betul sebelum berhenti Masa algoritma ialah O(k)(1<k<=n).

Kesedaran situasi ini ialah:

 1)遍历第一个数2, target - 2 = 9 - 2 = 7
 2)判断7是否在map,发现不在,把2加入map,继续遍历
 3)直到遍历到7, target - 7 = 9 - 7 = 2
 4)判断2在map,返回正确结果
 注意,要遍历到第二个正确数.
小葫芦

Tidak Key 的情况下,HashMap.containsKey(Key) 返回的是 false 不包括 Key.

    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

Tiada ralat penunjuk nol seperti yang anda fikirkan.

Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan